Unit 3, Part 1 of 2 · CEUC302 Theory of Computation
One string, how many trees?
Chapter 1 introduced grammars just enough to define the Chomsky hierarchy. This chapter is where context-free grammars become the main character. One example carries all four sections: the arithmetic expression id + id * id, and the two rival grammars that can generate it — one natural but ambiguous, one slightly more work to write but not. Getting from the first grammar to the second, and knowing exactly when that's even possible, is most of what this chapter teaches.
The problem
Same string, genuinely different structure
E → E+E | E*E | id generates "id+id*id" two structurally different ways.
Both trees are completely legal under the grammar. One groups the multiplication first (mathematically correct); the other groups the addition first (wrong, but the grammar can't tell). Section 4.3 makes this precise and Section 4.4 asks whether it can always be fixed.
Before you start
This chapter picks grammars back up from Section 1.2 — non-terminals, production rules, derivations, sentential forms, and the one-line definition of ambiguity all carry over unchanged. What's new is depth: full leftmost/rightmost derivations, the standard arithmetic-expression and dangling-else disambiguation techniques, and the harder question of when ambiguity can't be designed away at all.
What "context-free" actually restricts
Chapter 1 used grammars to sort languages into tiers. Now the grammar itself is the object being studied — designed on purpose, not just classified.
Section 1.2 defined a grammar as G = (V, Σ, R, S) with rules α → β. Section 1.3's Chomsky hierarchy then tightened this for Type 2: every rule must have a single non-terminal on the left. That single restriction is the entire content of the word "context-free," and this chapter spends real time on what it buys — and what it costs.
The intuition, no symbols yet
"Context-free" means a non-terminal always means the same thing, rewrites the same way, no matter what surrounds it. Compare this to Chapter 1's context-sensitive rule shape, αAβ → αγβ, where A's rewrite is allowed to depend on its neighbours α, β. A context-free E means "some arithmetic expression" identically whether it's sitting inside E+E or E*E or standing alone — its surroundings never change what it's allowed to become.
The formal treatment
A context-free grammar is G = (V, Σ, R, S) where every rule in R has the shape A → γ, A ∈ V, γ ∈ (V∪Σ)* — any string of terminals and non-terminals at all, with no restriction beyond "exactly one non-terminal on the left." Derivation (⇒), the reflexive-transitive closure ⇒*, sentential forms, and L(G) = {w∈Σ* : S⇒*w} are unchanged from Section 1.2 — this section just puts a real design problem in front of them.
Every arithmetic expression a student writes — id+id, (id+id)*id, id*id+id*id — is generated by this one non-terminal, rewritten differently depending only on which rule is chosen, never on where E happens to sit. That freedom from context is exactly why the same E can appear on the left, right, or wrapped in parens with no special-casing.
A second worked grammar · balanced parentheses
Gbal: V={S}, Σ={(,)}, start S, rule S → (S)S | ε. This generates exactly the strings of properly matched parentheses — every "(" has a later matching ")", never the reverse. Verified against direct balance-checking for every string up to length 8: zero mismatches. Keep this grammar in mind; Unit 4 builds the matching pushdown automaton for exactly this language.
Worked example · deriving "()()" from Gbal
Worked example
two "statements" back to backDon't confuse these
- "Context-free" doesn't mean "unrestricted." The single-non-terminal-on-the-left rule is a genuine, real restriction — Type 0 (Section 1.3) is what "no restriction" actually looks like. Context-free sits deliberately between the tightly-restricted Type 3 and the fully general Type 0.
- A derivation isn't finished while any non-terminal remains. Same trap as Chapter 1: "(S)S" mid-derivation is a sentential form, not a member of L(Gbal) — it still contains S.
- Writing a rule doesn't guarantee a parser can use it efficiently. A CFG defines a language completely independently of how easy it is to parse; some perfectly valid rule shapes (left recursion, for instance) cause real trouble for certain parsing strategies — a Chapter 5 concern, not a Chapter 4 one.
Practice · 4.1
Seven problems
direct → variation → interpretation → synthesis4.1.1 · Is the rule E → (E) alone (without the others) context-free? Why or why not?
Show solution
Yes. A single non-terminal E on the left, any string ((E), a mix of terminals and one non-terminal) on the right — matches the A→γ shape exactly. Context-freedom is a property of each rule's shape, not of how "interesting" the rule is.
4.1.2 · Write a CFG for the language of non-empty strings of balanced parentheses only (exclude ε).
Show solution
S → (S)S | (S) | () — drop the pure ε option and instead give two ways to end a chain: a group followed by more statements (S)S, or a single group with nothing after it, (S) or the base case (). One valid answer among several; any grammar generating exactly Dyck-minus-ε works.
4.1.3 · Variation: is αAβ → αγβ (Chapter 1's context-sensitive shape, with α,β both non-empty) ever also a valid context-free rule?
Show solution
Only if α and β are both actually empty — then the rule degenerates to A→γ, which is context-free. The moment either is non-empty, the left side has more than just one non-terminal on it, breaking the context-free shape.
4.1.4 · Variation: write a CFG for {anb : n≥0} (any number of a's, then exactly one b).
Show solution
S → aS | b. Each firing of S→aS peels off one a; the mandatory single b only appears when the base case fires, guaranteeing exactly one b at the end and never zero.
4.1.5 · Interpretation: a classmate says Gexpr "isn't really context-free because E+E depends on there being two E's around the +." What's the confusion?
Show solution
Context-freedom is about whether a non-terminal's own rewriting depends on its surroundings, not about how many symbols appear in a rule's right-hand side. E→E+E is one rule with A=E on the left and γ=E+E on the right — perfectly valid A→γ shape. "Context" in the technical sense means the symbols flanking a non-terminal being consulted to decide how it rewrites (as in αAβ→αγβ) — not "the rule happens to mention other symbols."
4.1.6 · Interpretation: does Gbal generate "(()"? Justify without a full derivation.
Show solution
No. "(()" has 2 open parens and 1 close paren — unbalanced, and every string Gbal derives has matched pairs by construction (each (S) contributes exactly one open and one matching close). Any unequal count is immediately disqualified without needing to attempt a derivation.
4.1.7 · Synthesis (challenge) · Gbal's rule S→(S)S has two S's on the right. Explain what each one is "responsible for" in the language, in your own words, and connect it to why the grammar needs both rather than just S→(S).
Show solution
The first S (inside the parens) handles whatever balanced content nests inside this particular pair of parentheses. The second S (after the closing paren) handles whatever balanced content comes after this pair, at the same nesting level. S→(S) alone could only ever produce a single, fully-nested chain like "((()))" — it could never produce side-by-side groups like "()()" , since there'd be no way to attach a second group after the first one closes. The second S is exactly what makes sequences of sibling groups possible.
A derivation is a path; the tree is the destination
Many different sequences of rule choices can build the exact same structure. Leftmost and rightmost are just the two most standard ways to walk it.
A derivation is a sequence of individual rewriting choices. At any sentential form with more than one non-terminal, there's a real choice about which one to rewrite next — that choice doesn't affect what the non-terminal eventually becomes, only the order events are narrated in. Two conventions make that order predictable enough to talk about precisely.
The intuition, no symbols yet
Picture assembling a piece of flat-pack furniture with two independent sub-assemblies, a leg and a shelf. You can build the leg first, then the shelf, or the shelf first, then the leg — the finished furniture is identical either way. A derivation with two separate non-terminals in its sentential form is exactly this: independent sub-structures, each eventually resolved, in whichever order you narrate the story.
The formal treatment
A leftmost derivation (⇒lm) always rewrites the leftmost non-terminal remaining in the sentential form. A rightmost derivation (⇒rm) always rewrites the rightmost. A parse tree is the derivation's shape, stripped of ordering: root labelled S, every internal node a non-terminal labelled with the rule applied, its children the symbols of that rule's right-hand side in order, and leaves the terminals (or ε) finally produced.
The tree is the real object; leftmost/rightmost are just two readings of it
Every parse tree has exactly one leftmost derivation and exactly one rightmost derivation that produce it — but also, usually, many other valid "mixed-order" derivations that rewrite non-terminals in some other sequence entirely. All of them build the identical tree. Leftmost and rightmost aren't the only legal orders; they're just the two standard ones worth naming, because Chapter 5's parsing algorithms are built to reconstruct exactly one of the two.
Worked example · one tree, two orders
Worked example
id+id*id, read two waysStep through both orders yourself
same tree, leftmost vs rightmost
fig 4.2 · interactiveDon't confuse these
- Leftmost and rightmost derivations of the same tree always end at the same string. If they didn't, they wouldn't be derivations of the same tree — the final string (the tree's "yield") is a property of the tree, not of which order you narrated its construction.
- "Leftmost" refers to the sentential form, not the rule. It never means "the leftmost symbol appearing in whichever rule you're about to use" — it means "scan the current sentential form left to right, rewrite the first non-terminal you hit."
- A derivation that's neither strictly leftmost nor rightmost is still valid. It builds the same tree by a different, unnamed order — not wrong, just not one of the two standard conventions.
Practice · 4.2
Seven problems
direct → variation → interpretation → synthesis4.2.1 · Write the leftmost derivation of "()()" from Gbal (Section 4.1), and compare it to the derivation already shown there.
Show solution
S ⇒ (S)S ⇒ ()S ⇒ ()(S)S ⇒ ()()S ⇒ ()(). Identical to Section 4.1's derivation — at every step there was only ever one non-terminal in the sentential form, so "leftmost" and "the only choice available" coincided the whole way.
4.2.2 · Write the rightmost derivation of the tree (id*id)+id (note: this is the other tree for a different string than the worked example — the string is "id*id+id").
Show solution
E ⇒ E+E ⇒ E+id ⇒ E*E+id ⇒ E*id+id ⇒ id*id+id. Rightmost always attacks the right non-terminal first: the outer "+id" resolves before the "E*E" on the left ever gets touched.
4.2.3 · Variation: for the same tree id+(id*id), write one valid derivation that is neither leftmost nor rightmost.
Show solution
One example: E ⇒ E+E ⇒ id+E (leftmost so far) ⇒ id+E*E ⇒ id+id*E (now attacking the left branch of the inner E*E rather than continuing consistently) ⇒ id+id*id. Any order that isn't "always leftmost" or "always rightmost" throughout qualifies — there are several valid answers.
4.2.4 · Variation: how many total derivation steps does any valid derivation (leftmost, rightmost, or mixed) of the tree id+(id*id) require? Why is this number order-independent?
Show solution
5 steps, always — one step per internal node of the tree (root E, left E, right E, and the two leaf-producing E's under it: 5 non-terminal nodes total, each needing exactly one rule application). The order you visit them in doesn't change how many there are to visit.
4.2.5 · Interpretation: a classmate's leftmost derivation of some string ends in a different final string than their rightmost derivation of "the same tree." What went wrong?
Show solution
They aren't actually derivations of the same tree — somewhere, a different rule got applied to some node in one derivation than in the other, silently building a different tree (and therefore a different final string) despite both being labelled "leftmost" and "rightmost" of the "same" thing. The fix is to re-derive both from the identical tree structure, not from memory of two separate derivation attempts.
4.2.6 · Interpretation: why does Section 4.2's tree diagram only need to define 5 non-terminal expansion events, when the tree has more than 5 nodes total?
Show solution
Terminal nodes (id, +, *) never get "expanded" — they're already fully resolved the moment their parent non-terminal is rewritten. Only non-terminal nodes require a rule application, so only they correspond to a derivation step; leaves just appear as a side effect.
4.2.7 · Synthesis (challenge) · Chapter 1, Problem 1.2.7 argued that a grammar with only one non-terminal alive at a time is automatically unambiguous. Using leftmost derivations, explain why "only one non-terminal alive at a time" also makes leftmost and rightmost derivations identical, step for step.
Show solution
If there's never more than one non-terminal in any sentential form, then "the leftmost non-terminal" and "the rightmost non-terminal" are, at every step, literally the same single symbol — there's no other candidate to disagree about. Both conventions are forced into making the identical choice every time, so the two derivations coincide exactly, not just in step count but symbol-for-symbol.
Two classic cases, and the fix for each
Ambiguity isn't rare or exotic — the most natural grammar for arithmetic and the most natural grammar for if-statements are both, by default, ambiguous.
Recall Chapter 1's definition: a grammar is ambiguous if some string it generates has more than one parse tree. Gexpr is ambiguous exactly this way — the hero section's two trees for "id+id*id" are both completely legal. This section works through why, and the standard technique for removing it, on two of the field's most-cited examples.
The intuition, no symbols yet
An ambiguous grammar hasn't encoded a real-world convention it's implicitly relying on. Mathematics has a convention — multiplication before addition — that Gexpr never wrote down; it just generates every grouping and hopes the reader picks the right one. Fixing ambiguity means writing that convention into the grammar's shape, so illegal groupings become underivable rather than merely undesirable.
Case 1 · arithmetic expressions
Gexpr: E → E+E | E*E | (E) | id treats + and * as equals, so nothing stops * from being grouped after + is chosen first. The fix is grammar restructuring by precedence level: one non-terminal per binding tightness, with tighter operators nested structurally deeper.
Left recursion in E→E+T (rather than E→T+E) is doing a second job at the same time: it makes chains of same-precedence operators group left-to-right. id+id+id can only parse as (id+id)+id under this rule, never id+(id+id) — matching the standard left-associative reading of addition.
Worked example
why the ambiguity is actually goneCase 2 · the dangling else
Gif: S → if E then S | if E then S else S | other has the same disease. For "if a then if b then x else y," nothing in the grammar says which "if" the one "else" belongs to.
reading 1 · else binds to the inner if
if b then x else y
The entire inner if-then-else is one self-contained unit; the outer if has no else of its own.
reading 2 · else binds to the outer if
if b then x else y
The inner if is bare (no else); the trailing else instead closes the outer if.
Universally, programming languages pick reading 1: else always binds to the nearest unmatched if. The fix restructures S into two flavours — a matched statement (every if inside it already has its else) and an unmatched one (some if inside it is still missing its else):
Since the whole string has only one else available, the outer if can never be Matched (that would need two else's, one for each nested if) — it's forced into Unmatched → if E then S, with its inner S free to consume "if b then x else y" as a complete Matched statement. Reading 2 has no derivation left; it's been designed out, not just discouraged.
Don't confuse these
- Relabelling rules isn't restructuring. Renaming E to Expr or adding a redundant rule that generates no new strings doesn't remove any ambiguity — only changing which structures are derivable at all does.
- Precedence is a grammar-shape fact, not a comment. "* binds tighter than +" has to be encoded via which non-terminal nests inside which (T inside E, never the reverse) — writing it as a side-note next to an unchanged Gexpr does nothing to the actual derivable trees.
- Associativity and precedence are two separate knobs. Precedence decides which operator groups first when they differ (* before +); associativity decides which side groups first when they're the same (left-to-right for + and *, by the usual convention). A grammar can get one right and the other wrong independently.
Practice · 4.3
Seven problems
direct → variation → interpretation → synthesis4.3.1 · Under Gexpr-fixed, which non-terminal would ever directly generate a "+": E, T, or F?
Show solution
E only — E→E+T is the sole rule mentioning +. T and F's rules never contain a + symbol at all.
4.3.2 · Is Gexpr-fixed left-associative or right-associative for *? Show it with "id*id*id."
Show solution
Left-associative. T→T*F is left-recursive, so "id*id*id" can only build as (id*id)*id — T expands to T*F first, and that inner T expands to T*F again, growing leftward each time, never rightward.
4.3.3 · Variation: rewrite Gexpr-fixed to make * right-associative instead, keeping precedence unchanged.
Show solution
Flip the recursion direction: T → F*T | F. Now "id*id*id" builds as id*(id*id) — the rightmost F is consumed last, growing the tree rightward. Precedence is untouched since T still only ever appears nested inside E, never the reverse.
4.3.4 · Variation: for "if a then if b then x," (no else at all), does the ambiguity in Gif even arise? Why or why not?
Show solution
No ambiguity — with no else present anywhere, there's nothing to disagree about attaching. The dangling-else problem specifically needs an else count strictly less than the if count in some sub-expression, creating a genuine choice about which if the else closes.
4.3.5 · Interpretation: a classmate "fixes" Gexpr by adding the rule E→E+E+E as a special case for triple sums. Does this remove any ambiguity?
Show solution
No — it adds an extra way to derive some strings (more ambiguity, if anything, since now "id+id+id" might have a third derivation route through the new rule) without removing either of the two original derivations. Fixing ambiguity requires restricting what's derivable, never just adding alternatives.
4.3.6 · Interpretation: does Gexpr-fixed generate any string Gexpr doesn't, or vice versa?
Show solution
No — L(Gexpr-fixed) = L(Gexpr) exactly. Disambiguation by restructuring is specifically the technique of changing the grammar (and therefore the derivable trees) while holding the language fixed. If the language changed too, that would be a different (possibly broken) grammar, not a fix.
4.3.7 · Synthesis (challenge) · Explain why the matched/unmatched restructuring for dangling-else is the same underlying idea as precedence-layering for expressions — both use extra non-terminals to encode a distinction the original single non-terminal couldn't express. What distinction does each new non-terminal capture?
Show solution
In Gexpr-fixed, splitting E into E/T/F encodes "how tightly bound is this sub-expression" — a fact the single E couldn't express about itself. In Gif-fixed, splitting S into Matched/Unmatched encodes "does this statement still have an else-slot open" — again a fact the single S couldn't express. Both fixes work by giving the grammar new non-terminals whose entire job is to carry exactly the piece of context (precedence level; matched-ness) that was previously invisible, forcing every derivation to respect it structurally rather than leaving it to the reader's judgment.
When there's no fix to find
Section 4.3 always found an unambiguous grammar. That was luck of the language, not a guarantee — a few languages have no unambiguous grammar at all.
Gexpr and Gif were ambiguous grammars for languages that, it turns out, have perfectly good unambiguous grammars too — Gexpr-fixed and Gif-fixed proved it. That raises the natural next question: is every context-free language rescuable this way? No. A small number genuinely aren't, and this section is about recognising the difference.
The intuition, no symbols yet
Some strings belong to a language for two completely unrelated reasons at once — not "the grammar phrased it two ways," but "there are two independent, equally valid arguments for membership, and neither argument is more correct than the other." No rewording of the grammar can merge two genuinely different reasons into one; at best, a grammar can only pick one reason to keep and discard the other, which changes the language, not just the grammar.
The formal treatment
A context-free language L is inherently ambiguous if every grammar generating L is ambiguous — not "the grammars we've tried," all of them, provably, with no exception. This is a much stronger claim than "this particular grammar is ambiguous," and it needs to be proven about the language itself, independent of any one grammar.
The standard example (stated, not fully proven here)
L = {aibjck : i=j or j=k}. A string qualifies if the a-count matches the b-count, or the b-count matches the c-count (or both). It's a known theorem that L is inherently ambiguous. The full proof needs a tool beyond this course's scope (Ogden's lemma, a refinement of the Pumping Lemma) — what's worth understanding here is why it's plausible, not the formal proof itself.
A string like a3b3c7 is in L for exactly one reason (i=j; j≠k), and every grammar's derivation of it can safely reflect that one reason. But a3b3c3 sits in both circles — it satisfies i=j and j=k simultaneously, independently. Any grammar checking "i=j" structurally (say, by pairing off a's against b's one at a time while leaving c's free) builds one shape of tree. Any grammar checking "j=k" structurally builds a different shape. Since both checks are separately, validly true for this string, both trees are legitimate — and no single grammar can be rewritten to recognise only the "right" one, because there isn't a right one; both reasons are equally real.
Don't confuse these
- An ambiguous grammar is not automatically evidence of inherent ambiguity. Gexpr and Gif were both ambiguous and both fixable — the overwhelming majority of ambiguous grammars you'll meet are exactly this ordinary, fixable kind.
- Inherent ambiguity is rare, not typical. Most context-free languages have some unambiguous grammar; this section's example is a specifically constructed exception used precisely because such languages are hard to find naturally.
- "I haven't found an unambiguous grammar yet" ≠ "none exists." The first is a statement about effort so far; the second requires an actual proof (typically via Ogden's lemma) that no grammar, however cleverly designed, could ever work.
Practice · 4.4
Seven problems
direct → variation → interpretation → synthesis4.4.1 · For L = {aibjck : i=j or j=k}, is "aabbbccc" (2 a's, 3 b's, 3 c's) in L? For how many reasons?
Show solution
i=2, j=3, k=3. i≠j (2≠3) but j=k (3=3). In L, for exactly one reason — no ambiguity is forced for this particular string.
4.4.2 · Is "aaabbbccc" (3,3,3) in L? For how many reasons?
Show solution
i=j=3 and j=k=3 — both conditions hold. This is exactly the doubly-justified case the overlap in fig 4.4 illustrates.
4.4.3 · Variation: is "abc" in L, and if so, for how many reasons?
Show solution
i=j=k=1. Both i=j and j=k hold — two reasons, the smallest non-trivial doubly-justified string in the language.
4.4.4 · Variation: write an unambiguous CFG for just the sub-language {aibjck : i=j} alone (dropping the "or j=k" half).
Show solution
S → AC; A → aAb | ε; C → cC | ε. A pairs off a's and b's one-for-one (guaranteeing i=j exactly), then C tacks on any number of c's, completely unconstrained. Only one derivation exists per string — this half alone is not inherently ambiguous, which is precisely why the union with the other half is where the trouble starts.
4.4.5 · Interpretation: a classmate says "L must be inherently ambiguous because the grammar I wrote for it, using two separate sub-grammars joined by a union rule, is ambiguous." What's missing from this argument?
Show solution
It only shows one grammar is ambiguous, exactly the gap Section 4.4's trap box warns about. Proving inherent ambiguity requires ruling out every possible grammar, including cleverer ones nobody has tried yet — a claim about the language, which needs its own dedicated proof technique (Ogden's lemma), not just one failed attempt at disambiguation.
4.4.6 · Interpretation: does inherent ambiguity mean the language isn't context-free after all?
Show solution
No. Inherently ambiguous languages are still fully context-free — they have context-free grammars, plenty of them, just none that happen to be unambiguous. Regularity/context-freedom (Chapter 1's hierarchy) and ambiguity (a property of grammars, extended here to "of every possible grammar for a language") are entirely separate axes.
4.4.7 · Synthesis (challenge) · Explain why {aibjck : i=j} alone (Problem 4.4.4) and {aibjck : j=k} alone are each individually unambiguous, yet their union is inherently ambiguous. What does this reveal about closure properties and ambiguity together?
Show solution
Context-free languages are closed under union (a Chapter 5 result, mirroring Section 3.1's regular-language closures) — the union is guaranteed to still be context-free. But closure properties only promise the result stays in the class; they promise nothing about ambiguity being preserved. Combining two individually well-behaved (unambiguous) languages can produce a language where no single grammar can cleanly track "which original piece this string came from," because for strings in the overlap, it genuinely came from both at once. Being closed under an operation and staying "nicely disambiguatable" under that operation are two independent guarantees, and only the first one is actually promised.
Cheat sheet
One line per idea. If a line doesn't ring a bell, that section needs a re-read before Chapter 5.
CFGs, formally · 4.1
every rule: A → γ, exactly one non-terminal on the left
"context-free" = a non-terminal rewrites the same way regardless of surroundings
Gexpr: E→E+E|E*E|(E)|id · Gbal: S→(S)S|ε
a valid rule shape doesn't guarantee an easy-to-parse grammar (Chapter 5)
Derivations & trees · 4.2
leftmost: always rewrite the leftmost non-terminal; rightmost: the rightmost
the tree is the real object; derivation order is just a narration of it
same tree ⇒ same step count, same final string, any valid order
mixed-order derivations are valid too, just unnamed conventions
Ambiguity & fixes · 4.3
ambiguous = some string has ≥2 parse trees under this grammar
precedence: one non-terminal per binding level, tighter nested deeper
associativity: recursion direction (T→T*F left; F*T right)
dangling else: split S into Matched/Unmatched to force nearest-if binding
Inherent ambiguity · 4.4
inherently ambiguous = every grammar for this language is ambiguous
rare; most ambiguous grammars are the ordinary, fixable kind
classic example: {aibjck : i=j or j=k}
still context-free — ambiguity and hierarchy tier are independent axes
Ten questions, no section labels
Exams don't tell you which lecture a question came from. Neither does this.
ST1 · Is the rule "aA → aB" (a a terminal, A and B non-terminals) context-free?
Show solution
No. The left side "aA" has two symbols, not a single non-terminal — it doesn't match the A→γ shape required by Section 4.1's definition.
ST2 · In one sentence, what's the difference between a parse tree and a derivation?
Show solution
The tree is the finished structure (which rule fired at which node); a derivation is one particular ordered narration of building that structure, one non-terminal expansion at a time.
ST3 · How many distinct parse trees does Gexpr have for "id*id*id*id"?
Show solution
5 — four id's joined by three *'s gives Catalan(3)=5 distinct binary groupings (verified by brute-force enumeration), the same Catalan pattern Chapter 1's S→SS|a example first showed.
ST4 · True or false: leftmost and rightmost derivations of the same parse tree always take the same number of steps.
Show solution
True. Step count equals the number of non-terminal nodes in the tree — a property of the tree, not of the order it's narrated in.
ST5 · Does Gexpr-fixed generate any string that Gexpr doesn't (or vice versa)?
Show solution
No. Restructuring for disambiguation preserves the language exactly; only the set of derivable trees per string shrinks.
ST6 · "if a then if b then if c then x else y" — under the standard convention, which if does the else bind to?
Show solution
The innermost if (if c) — else always binds to the nearest unmatched if, applied from the inside out: if c then x else y, wrapped unchanged inside "if b then …", wrapped unchanged inside "if a then …".
ST7 · Is "aabbcc" in L={aibjck : i=j or j=k}? For how many reasons?
Show solution
i=j=k=2. Yes, for two reasons — both i=j and j=k hold independently.
ST8 · Fill in: precedence decides ______; associativity decides ______.
Show solution
Precedence decides which operator groups first when they're different (e.g. * before +). Associativity decides which side groups first when operators are the same (e.g. left-to-right for repeated +).
ST9 · Does having more production rules make a grammar more likely to be ambiguous?
Show solution
Not inherently. Ambiguity depends on whether some string admits two distinct derivations, which is about rule shape and overlap, not rule count. A grammar with many rules can be perfectly unambiguous; a grammar with very few (like Gexpr's four) can be badly ambiguous.
ST10 · Is every inherently ambiguous language automatically not context-free?
Show solution
No. Inherently ambiguous languages are still context-free by definition (they have context-free grammars, just none unambiguous). Chomsky-hierarchy tier and ambiguity are independent properties.
Where this goes next
- Chapter 5 puts Gexpr-fixed's shape to work: Chomsky Normal Form and Greibach Normal Form standardise every grammar into a uniform rule shape.
- The Pumping Lemma returns, now for context-free languages — a genuinely different argument than Chapter 3's regular version.
- Parsing algorithms (top-down, and the CYK bottom-up method) turn "does a derivation exist" into something a program can actually run.
Further reading
- Sipser, Introduction to the Theory of Computation, 3rd ed. — the context-free grammars chapter covers ambiguity and ambiguous-vs-inherently-ambiguous with the same core examples used here.
- J. C. Martin, Introduction to Languages and the Theory of Computation. — a solid second source specifically for the precedence/associativity grammar-restructuring technique, with additional worked expression grammars.
Next: Chapter 5 · CFG II — CNF/GNF, Pumping Lemma & Parsing