Grammars: Summary
Grammar
Form of rules x ® y
Unrestricted
x Î (N È T)*N(N È T)*
y Î (N È T)*
Context-sensitive
x Î (N È T)*N(N È T)*
y Î (N È T)*, |x| £ |y|
Context-free
Right-Linear
Languages
Recursively enumerable
Context-sensitive
Context-free
Regular
Generalization
Restriction
36/45