Unrestricted Grammar

Aka. phrase-structure grammar. A 4-tuple $G = (V, \Sigma, S, P)$ where:

• $V$ — non-terminals
• $\Sigma$ — terminals
  $V$ and $\Sigma$ are disjoint.
• $S$ — start symbol
• $P$ — productions
  $\alpha \to \beta$ where $\alpha, \beta \in (V \cup \Sigma)^*$ and $\alpha$ contains $\geq 1$ non-terminal

A relaxation over CFGs where, on LHS of productions, more than 1 non-terminals may occur.

For any recursively-enumerable language $L$, there exists an unrestricted grammar $G$ generating $L$.

For any unrestricted grammar $G$, there exists a Turing machine $T$ that accepts the same language.