Context-sensitive, context-free, regular grammars

A grammar G = (V, T, P, S) has non-terminals V, terminals T, productions P and start symbol S. Chomsky classified grammars by the form of their productions.

Definitions

• Context-sensitive grammar (Type 1): every production is αAβ → αγβ, with γ non-empty. Equivalently |LHS| ≤ |RHS| (non-contracting; S → ε is allowed only if S never appears on a right side). A is replaced by γ only in the context α…β.
• Context-free grammar (Type 2): every production has the form A → γ, where A is a single non-terminal and γ is any string of terminals and non-terminals.
• Regular grammar (Type 3): every production is A → aB or A → a (right-linear), or A → Ba or A → a (left-linear), also A → ε. At most one non-terminal in the right side, and always at the same end.

Examples

• Context-sensitive, generating { aⁿbⁿcⁿ : n ≥ 1 }: S → aSBC | aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc. (CB → BC has a two-symbol left side, so it is not context-free.)
• Context-free, generating { aⁿbⁿ : n ≥ 0 }: S → aSb | ε.
• Regular, generating strings over {a, b} ending in ab: S → aS | bS | aA, A → b.

Differences

Hierarchy: Regular ⊂ Context-free ⊂ Context-sensitive ⊂ Unrestricted (Type 0). Every regular language is context-free, but { aⁿbⁿ } is context-free and not regular; { aⁿbⁿcⁿ } is context-sensitive and not context-free.