Unrestricted Grammars

What made context-free grammars “context-free” was that the left-hand side of each rule consisted of only a single variable, allowing substitution for that variable wherever it appears in a derivation, i.e., independent of its “context.” An unrestricted grammar (aka “Type 0 grammar”) allows multiple symbols, both terminals (except for λ, which serves no purpose on the rule’s left-hand side) and nonterminals, on the left-hand side of rules, allowing substitution to be sensitive to the context surrounding variables. For example, the rule $Ra\to aR$ allows swapping those two symbols in a derivation, but only applies when the variable $R$ is followed immediately by the symbol $a$.

Definition of unrestricted grammar

An unrestricted grammar is a rewriting system with rules of the form $s\to t$, where $s,t\in (\Sigma\cup V)^+$ (except $t$ could also be $\lambda$) and $s$ contains at least one variable from $V$.

The following unrestricted grammar generates $\{a^nb^nc^n \;|\; n \geq 0\}$: