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
x Î N
y Î (N È T)*
Right-Linear
x Î N
y Î T* È T*N
Languages
Recursively enumerable
Context-sensitive
Context-free
Regular
Textové pole: Generalization
Generalization
Textové pole: Restriction
Restriction
36/45