Context-free grammars, derivations and ambiguity
Goals and notation
Build grammars, prove their languages, and distinguish ambiguity of a grammar from properties of its language. A CFG G=(V,Σ,P,S) has finite variables V, terminal alphabet Σ disjoint from V, finite productions P and start variable S. Each rule A→α replaces a single variable A by a string α∈(V∪Σ)*. Empty α is written ε. A sentential form may contain variables; a word in L(G) contains only terminals and is derivable from S in finitely many steps.
A leftmost derivation always replaces the leftmost remaining variable; a rightmost derivation does the analogous thing on the right. A parse tree records hierarchical rule choices, not the order in which independent variable occurrences were expanded. Leaves read left-to-right give the terminal word, with ε contributing no symbol.
1. Worked grammar and two-sided proof
For L={a^n b^n:n≥0}, use S→aSb | ε. Example: S⇒aSb⇒aaSbb⇒aabb. Each recursive rule adds one a to the left and one b to the right. After k recursive rules, the sentential form is a^k S b^k; the ε-rule finishes with a^k b^k. Thus every generated word belongs to L. Conversely, applying the recursive rule n times and then ε generates every a^n b^n. These two arguments prove equality, rather than only exhibiting sample members.
To generate {a^i b^j:i,j≥0}, use S→AB, A→aA|ε, B→bB|ε. Here the counts are independent. Replacing S→aSb|ε with two independent variables changes the language: abbb now appears.
2. Different derivation orders are not automatically ambiguity
For S→AB, A→a, B→b, the derivations S⇒AB⇒aB⇒ab and S⇒AB⇒Ab⇒ab differ only in expansion order and share one parse tree. A CFG is ambiguous if some terminal word has at least two distinct parse trees, equivalently at least two leftmost derivations or at least two rightmost derivations. It is not enough to find one leftmost and one rightmost derivation.
For E→E+E | EE | id, word id+idid has two trees. One uses root production E→E+E and groups id+(idid), with + as the top-level operator; another uses E→EE and groups (id+id)*id, with * as the top-level operator. The parse-tree root itself is the variable E in both cases. The grammar specifies neither precedence nor associativity. Trees matter because attaching evaluation rules would give different meanings for suitable values.
3. Repairing expression structure
Use E→E+T|T, T→TF|F, F→(E)|id. Multiplication is confined within terms, so it binds more tightly than addition; left recursion gives left associativity at each operator level. For id+idid, the root production is E→E+T and the final T expands to T*F. The parentheses alternative permits explicitly overriding precedence. The repair changes parse structure while retaining the intended ordinary expression language.
Do not conclude that a language is inherently ambiguous merely because one grammar is ambiguous. Inherent ambiguity means every CFG for that language is ambiguous. For example, {a^n b^n:n≥0} has the unambiguous grammar already shown, regardless of whether someone supplies a redundant ambiguous grammar for it.
4. Grammar design from cases
For L={a^i b^j c^k:i=j or j=k; i,j,k≥0}, split into two cases. S→XC | AY, X→aXb|ε, C→cC|ε, A→aA|ε, Y→bYc|ε. The first branch equates a and b counts; the second equates b and c. Words a^n b^n c^n belong to both cases and have two trees in this grammar. This demonstrates ambiguity of this construction, without by itself proving that no alternative unambiguous grammar exists.
Pitfalls
- A grammar rule's left side in a CFG is exactly one variable.
- A variable-free derivation is required for membership; merely reaching a sentential form is insufficient.
- Prove both inclusion directions when claiming a grammar generates exactly a language.
- Grammar ambiguity and language inherent ambiguity have different quantifiers.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. S→aSb|ε generates which language?
A. ab B. {a^n b^n:n≥0} C. {a^n b^n:n≥1} D. {a^n b^(2n):n≥0}
Answer: B
A: Counts cannot vary independently.
B: Each recursion adds one of each and ε allows n=0.
C: The grammar also generates ε.
D: The rule adds one b, not two.
P02. Two unrestricted derivations differing only in independent expansion order show:
A. The grammar is necessarily ambiguous B. The language is non-context-free C. No ambiguity conclusion by themselves D. Every word has two trees
Answer: C
A: They may describe the same tree.
B: Derivation order does not affect context-freeness.
C: Distinct trees or two same-direction derivations are needed.
D: Nothing here establishes different trees.
P03. The ambiguous expression grammar can parse id+id*id with which top-level operators?
A. Only + B. Only * C. Both + and * D. Only id
Answer: C
A: A parse with * as the top-level operator also exists.
B: A parse with + as the top-level operator also exists.
C: The two groupings yield + and * as possible top-level operators.
D: The entire word is not one id.
P04. In E→E+T|T and T→T*F|F, which operator binds more tightly?
A. + B. * C. Both are unconstrained D. Neither can occur
Answer: B
A: Addition combines complete terms.
B: Multiplication occurs inside terms before their addition.
C: The variable levels enforce precedence.
D: Both productions explicitly include operators.
P05. Inherent ambiguity of L means:
A. Some CFG for L is ambiguous B. Every CFG for L is ambiguous C. L has infinitely many words D. L has no CFG
Answer: B
A: One poor grammar does not settle the language property.
B: The universal quantifier over CFGs is essential.
C: Infinite languages can be unambiguous.
D: The term applies to context-free languages.
P06. For S→AB,A→aA|ε,B→bB|ε, which word is generated?
A. ba B. abab C. abbb D. baba
Answer: C
A: An a cannot follow a b.
B: The second a violates block order.
C: Independent counts allow one a and three b.
D: The order alternates rather than a-block then b-block.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in