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

Productions $\alpha \to \beta$ impose no length constraint. Both the LHS and RHS can contain any mix of terminals and non-terminals.

LHS must contain $\ge 1$ non-terminal. This is the only restriction.

Equivalence to Turing Machines

• 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$ accepting the same language.

Unrestricted grammars generate exactly the recursively-enumerable languages.

Example

The language $L = \{a^n b^n c^n \mid n \ge 1\}$ is not context-free but is generated by an unrestricted grammar. The grammar uses non-terminals to enforce equal counts across 3 symbol types by rewriting across the string.

A simpler example: $L = \{ww \mid w \in \{a,b\}^+\}$ (strings that are the concatenation of a word with itself).

Productions (sketch):

• $S \to AB$ — separate the 2 halves
• $A \to aA \mid bA \mid \lambda$ — generate first half
• $B \to aB \mid bB \mid \lambda$ — generate second half
• Synchronization rules force $A$ and $B$ to produce the same string

Full grammars for such languages use auxiliary non-terminals and cross-symbol rewriting that no CFG production $A \to \alpha$ can simulate.