Unrestricted Grammar

• def. If $G$ is an Unrestricted Grammar, then $L(G)$ is recursively enumerable [=TM equivalent]. This is equivalent to all productions following the form:

$$(V\cup T{)}^{+}\to (V\cup T{)}^{\ast }$$

def. $G$ is a Context-Sensitive Grammar if its productions follow the form:

$$\begin{gathered} (V\cup T{)}^{+}\to (V\cup T{)}^{\ast } \\ \text{and} \\ |LHS|\le |RHS| \\ \text{and} \\ \text{there is no }\lambda \text{ in the RHS} \end{gathered}$$