Unrestricted grammar; superset of CFG

Unrestricted grammar (Type-0 grammar)

An unrestricted grammar is G = (V, T, P, S), where V is the set of variables, T the terminals, S ∈ V the start symbol, and every production has the form

α → β, with α ∈ (V ∪ T)⁺ containing at least one variable, and β ∈ (V ∪ T)*.

There is no restriction on the length or shape of α and β; the left side may be a string of several symbols (so rules can depend on context), and β may be shorter than α (erasing rules). L(G) = { w ∈ T* : S ⇒* w }.

Unrestricted grammars generate exactly the recursively enumerable languages, the languages accepted by Turing machines.

Example: L = { aⁿbⁿcⁿ : n ≥ 1 }

S  → aSBC | aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

Derivation of aabbcc: S ⇒ aSBC ⇒ aaBCBC ⇒ aaBBCC (CB → BC) ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc. The rule CB → BC has a two-symbol left side, so this grammar is not context free (and indeed no CFG exists for L).

Is an unrestricted grammar a superset of CFG?

Yes. In a CFG every production has the form A → β with A a single variable. This satisfies the requirement of an unrestricted grammar (the left side contains at least one variable). So every CFG is already an unrestricted grammar, and every CFL is a Type-0 language.

The inclusion is proper: the grammar above generates { aⁿbⁿcⁿ }, which is not context free (by the pumping lemma). Hence

regular ⊂ context free ⊂ context sensitive ⊂ unrestricted (recursively enumerable).