Exercises — Context-free grammars (CFG) — productions, derivations, parse trees

• Variable (non-terminal): a placeholder still to be expanded, e.g. $S,E,T$.
• Terminal: a real letter of the final string, e.g. a, (, +.
• Production: a rewrite rule $A\to \alpha$; the left side is exactly one variable.
• Derivation: $S\Rightarrow \cdots \Rightarrow w$, applying one production per step.
• Parse tree: the structural picture — who is the child of whom; its yield (leaves left-to-right) is the derived string.

The single test: the left-hand side must be exactly one variable.

• (a) valid — LHS is the single variable $S$; the right side may mix terminals and variables freely.
• (b) invalid — LHS is aS, a terminal glued to a variable. That's context-sensitive, not context-free.
• (c) valid — LHS is $S$; RHS $\epsilon$ (empty string) is allowed. This is an erasing rule.
• (d) invalid — LHS AB is two variables. Not a single variable ⇒ not a CFG.

Answer: valid = (a), (c); invalid = (b), (d).

• (a) sentential form — it still contains the variable $S$, so it is a partway string, not a finished word. It appears literally after one step: $S\Rightarrow (S)S$.
• (b) finished word, in $L(G_1)$ — only terminals, and it is derivable (parent's Worked Example 1 derived exactly (())).
• (c) neither — )( is all terminals so it's not a sentential-form-with-variables, but $G_1$ can never open with ). Every non-empty derivation starts $S\Rightarrow (S)S$, forcing a ( first. So it is not in $L(G_1)$.

Leftmost = at each step rewrite the leftmost remaining variable. $S\Rightarrow (S)S\Rightarrow ()S\Rightarrow ()(S)S\Rightarrow ()()S\Rightarrow ()()$ Step-by-step:

1. $S\to (S)S$ — start the first group.
2. leftmost $S\to \epsilon$ — the first group is empty ⇒ ().
3. remaining $S\to (S)S$ — start a second group after it.
4. its leftmost $S\to \epsilon$ — second group empty ⇒ ()().
5. final trailing $S\to \epsilon$ — nothing left to add. Yield ()() ✓.

$S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ Each use of $S\to aSb$ wraps one a on the left and one b on the right — a matched pair around the middle. Applying it $n$ times then $S\to \epsilon$ gives $a^n{b}^n$. Language: $L(G_A)=\{a^n{b}^n\mid n\ge 0\}$ — equal numbers of a's then b's. This is the classic language no DFA can recognise (it needs to count $n$).

Derive 000111: $S\Rightarrow 0S1\Rightarrow 00S11\Rightarrow 000111$ Last step used $S\to 01$. So yes, 000111 $\in L(G_B)$. Is $\epsilon$ in it? The only terminating rule is $S\to 01$, which emits at least one 0 and one 1. There is no $S\to \epsilon$ rule. So the shortest word is 01, and $\epsilon \notin L(G_B)$. Hence $L(G_B)=\{0^n{1}^n\mid n\ge 1\}$ (note $n\ge 1$, not $0$).

Tree A groups the left + first — structure $(a+a)+a$: $E\Rightarrow E+E\Rightarrow (E+E)+E\Rightarrow \cdots \Rightarrow (a+a)+a$ Tree B groups the right + first — structure $a+(a+a)$: $E\Rightarrow E+E\Rightarrow a+E\Rightarrow a+(E+E)\Rightarrow \cdots \Rightarrow a+(a+a)$ These are two different shapes: in Tree A the top node's children are (a+a) and a; in Tree B they are a and (a+a). See the two family-photos below.

Because one string a+a+a yields two structurally distinct trees, $G_2$ is ambiguous. (For plain + the two groupings give the same numeric value, but the grammar is still ambiguous — ambiguity is about tree shape, not final value.)

No. They are the same tree, walked in a different order. Recall the parent's key fact: every parse tree ↔ exactly one leftmost derivation. To test ambiguity you must produce two distinct leftmost (or tree-distinct) derivations — not two derivations that merely differ in which variable you expanded first. Reduce both (i) and (ii) to their leftmost form: both become $S\Rightarrow (S)S\Rightarrow ((S)S)S\Rightarrow ((S))S\Rightarrow (())S\Rightarrow (())$ i.e. one identical leftmost derivation ⇒ one tree. (()) has a unique tree in $G_1$. No ambiguity shown.

Idea: one a must summon two b's, and they must stay balanced around the recursion. Wrap a on the left and bb on the right each step: $S\to aSbb\mid abb.$

• $S\to aSbb$ adds one a and two b's, keeping structure nested.
• $S\to abb$ is the base case ($n=1$), so $\epsilon$ is excluded (matches $n\ge 1$).

Derive aabbbb ($n=2$): $S\Rightarrow aSbb\Rightarrow aabbbb=aabbbb✓$

A palindrome is either empty, a single letter (odd centre), or the same letter on both ends wrapping a smaller palindrome: $S\to 0S0\mid 1S1\mid 0\mid 1\mid \epsilon .$

• $0S0,1S1$: peel a matching pair off both ends.
• $0,1$: odd-length centres.
• $\epsilon$: even-length centre / empty word.

Check 0110: $S\Rightarrow 0S0\Rightarrow 01S10\Rightarrow 0110$ (last step $S\to \epsilon$). ✓ And 010: $S\Rightarrow 0S0\Rightarrow 010$ (using $S\to 1$). ✓

"or" ⇒ two independent cases, joined by a top choice. Give $S$ two alternatives.

Case $i=j$ (match a,b; then any number of c's): $X\to aXb\mid \epsilon ,C\to cC\mid \epsilon ,S_1\to XC.$ Case $j=k$ (any a's; match b,c): $A\to aA\mid \epsilon ,Y\to bYc\mid \epsilon ,S_2\to AY.$ Top rule: $S\to S_1\mid S_2.$ The single top-level choice $S\to S_1\mid S_2$ is the logical "or". (Note: this grammar is ambiguous on strings like abc satisfying both — that's fine; the task only asked to generate $L$, not for an unambiguous grammar.)

Unique leftmost derivation: $E\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T\Rightarrow a+T\Rightarrow a+T\ast F\Rightarrow a+F\ast F\Rightarrow a+a\ast F\Rightarrow a+a\ast a$ Why forced? + can appear only at the $E$ level ($E\to E+T$), and * only at the $T$ level ($T\to T\ast F$). To place the single + you must split at the top into $E+T$; the right operand of + is a $T$, and only a $T$ can hold the *. So a*a is forced to sit below the + as one $T$ — grouping $a+(a\ast a)$. No other split is legal, so exactly one tree exists.

Because there is exactly one parse tree (one leftmost derivation), $G_3$ produces a+a*a unambiguously, and * binds tighter than + — precisely the intended precedence.

A tree corresponds to a full parenthesisation of a+a+a+a — i.e. a way to bracket 4 leaves so that every internal + node has two children. This count is the Catalan number $C_n$ for $n$ internal + operators, where $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. Here $n=3$ (three +), so $C_3=\frac{1}{4}\left(\genfrac{}{}{0ex}{}{6}{3}\right)=\frac{1}{4}\cdot 20=5.$ Answer: 5 distinct parse trees. The five bracketings: $((a+a)+a)+a,(a+(a+a))+a,(a+a)+(a+a),a+((a+a)+a),a+(a+(a+a))$. This is exactly why ambiguity explodes: the number of trees grows like Catalan numbers, so a compiler with an ambiguous grammar faces exponentially many interpretations. That is why real languages use layered grammars like $G_3$ (see Compilers — parsing).

Idea: first generate matched pairs $ab$ (the part where $n=m$), then allow extra leading a's to push $n$ above $m$. $S\to aSb\mid aS\mid \epsilon .$

• $S\to aSb$: one matched pair (keeps $n=m$ growing).
• $S\to aS$: an extra a with no b (raises $n$ over $m$).
• $S\to \epsilon$: stop.

Because every b is produced only alongside a leading a (rule 1), and rule 2 adds a's with no b, we always have $n\ge m$. Also all a's stay left of all b's (rule 1 wraps b to the far right, rule 2 adds a on the left).

Boundary word aab ($n=2,m=1$): $S\Rightarrow aS\Rightarrow aaSb\Rightarrow aa\epsilon b=aab$. ✓ Smallest word: $S\Rightarrow \epsilon$, so $\epsilon \in L$ ($n=m=0$). ✓