Context Sensitive Grammars & Unrestricted Grammars
- Unrestricted Grammars are the largest family of grammars in the
Chomsky hierarchy. The languages described by them are the
recursively enumerable languages (r.e. languages).
- Unrestricted grammars have production rules of the form:
a -> b, which a and b arbitrary
strings of grammar symbols.
- Context Sensitive Grammars are a subset, with the additional rule
that of production rules a -> b, the length of b has
to be at least the length of a. Context Sensitive Grammars
describe Context Sensitive Languages.
- Almost all concievable languages are Context Sensitive Languages.
- Recursively enumerable languages require a Turing Machine to parse, while
Context Sensitive Languages can be parsed with a Linear Bounded
Automaton; a Turing Machine with a finite amount of tape.