Context-Sensitive
Grammar
Definition:
Let G = (N, T, P, S) be an unrestricted
grammar. G is a
context-sensitive (or length-increasing) grammar (CSG) if every rule x ® y Î P satisfies |x| £ |y|.
Restriction of URG
Gist:
Note: Þ, Þn, Þ+, Þ* and L(G) are
defined by analogy with the definitions of
the corresponding notions on URGs.
30/45