- 2071 Chaitra
CFG versus unrestricted grammar
Short answer
CFG rules have a single variable on the left (A→α). Unrestricted grammar allows any non-empty string containing at least one variable (α→β). CFGs generate context-free languages like aⁿbⁿ; unrestricted grammars generate recursively enumerable languages like aⁿbⁿcⁿ with rules such as CB→BC.
What is the difference between a CFG and an unrestricted grammar? Give an example.
A context free grammar (CFG) has productions A → α, where the left side is a single variable and α is any string of terminals and variables. An unrestricted grammar (Type 0) has productions α → β, where α is any non-empty string containing at least one variable, and β is any string.
| Point | CFG | Unrestricted grammar |
|---|---|---|
| Left side of rule | exactly one variable | any string with at least one variable |
| Rule form | A → α | α → β |
| Context | replacement independent of context | replacement may depend on neighbours |
| Language class | context free languages | recursively enumerable languages |
| Machine | pushdown automaton | Turing machine |
| Shrinking the string | only by A → ε (one variable erased at a time) | any rule with β shorter than α, so strings can grow and shrink freely |
| Parse tree | exists for every derivation | does not exist in general |
| Example language | { aⁿbⁿ } | { aⁿbⁿcⁿ } |
Examples
- CFG for { aⁿbⁿ : n ≥ 0 }: S → aSb | ε.
- Unrestricted grammar for { aⁿbⁿcⁿ : n ≥ 1 }:
S → aSBC | aBC
CB → BC
aB → ab bB → bb
bC → bc cC → cc
The rule CB → BC has a left side of two symbols, which no CFG allows. Every CFG is an unrestricted grammar, but not the other way round, since { aⁿbⁿcⁿ } is not context free.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Unrestricted grammar; superset of CFG · Theory of Computation, chapter 4 · asked 2×
- Define CFG with example · Theory of Computation, chapter 3 · asked 2×
- CFG for aᵐbⁿ with m ≥ n · Theory of Computation, chapter 3 · asked 2×
- CFG for aⁿb^(2n); parse tree · Theory of Computation, chapter 3 · asked 2×