Context-free grammars and push-down automata

Context-free grammars

Definition. A CFG is (V,Σ,P,S), where variables V can be replaced according to productions, terminals Σ form output strings, P is the production set, and S is the start variable. A derivation repeatedly replaces one variable; the generated language contains terminal strings derivable from S.

Example. S→aSb | ε generates {aⁿbⁿ:n≥0}.

Exam point. A production such as A→aAb has one variable on its left side, which is the defining CFG restriction.

Solved examples

Example 1 — derive a string. Use S→aSb | ε to derive aaabbb.

1. S⇒aSb.
2. Replace the inner S: aSb⇒aaSbb.
3. Replace again: aaSbb⇒aaaSbbb.
4. Use S→ε: aaaSbbb⇒aaabbb.
5. The derivation has three recursive uses and one terminating use.

Example 2 — determine membership. Does the grammar S→aSb|ε generate aabbb?

1. Each recursive production adds exactly one a on the left and one b on the right.
2. The terminating production removes S without adding symbols.
3. Therefore every generated string has equal counts of a and b and all a's precede b's.
4. No; the counts differ.

Parse trees and ambiguity

Definition. A parse tree records production applications with variables as internal nodes and terminals as leaves. A grammar is ambiguous if some string has two distinct parse trees, equivalently two distinct leftmost derivations or two distinct rightmost derivations.

Example. E→E+E | E*E | id is ambiguous because id+id*id can group in two ways.

Exam point. Multiple derivation orders can describe the same parse tree; ambiguity requires distinct structures, not merely different replacement order.

Solved examples

Example 1 — two parses. Show ambiguity for id+id*id in the expression grammar above.

1. One root split uses E→E+E; the right child derives id*id. This gives id+(id*id).
2. Another root split uses E→E*E; the left child derives id+id. This gives (id+id)*id.
3. Both yield the same terminal string but have different root operators.
4. The grammar is ambiguous.

Example 2 — remove ambiguity with precedence. Give a grammar where * binds tighter than + and both are left associative.

1. Let E→E+T | T handle addition.
2. Let T→T*F | F handle multiplication.
3. Let F→(E) | id handle atoms.
4. The separated levels force multiplication below addition in the parse tree; left recursion gives left associativity.

Leftmost and rightmost derivations

Definition. A leftmost derivation always expands the leftmost remaining variable; a rightmost derivation expands the rightmost. For a fixed parse tree, each convention gives a unique derivation sequence.

Example. For S→AB, A→a, B→b, the leftmost sequence is S⇒AB⇒aB⇒ab.

Exam point. Keep terminal symbols fixed while selecting the next variable to expand.

Solved examples

Example 1 — leftmost derivation. Grammar S→AB, A→aA|a, B→b; derive aaab leftmost.

1. S⇒AB.
2. Expand A: AB⇒aAB.
3. Expand the leftmost A again: aAB⇒aaAB.
4. Terminate A: aaAB⇒aaaB.
5. Expand B: aaaB⇒aaab. Answer: the displayed leftmost derivation.

Example 2 — rightmost derivation. For the same grammar, derive aab rightmost.

1. S⇒AB.
2. Expand rightmost B: AB⇒Ab.
3. Expand A and terminate it as aA: Ab⇒aAb.
4. Replace A with a: aAb⇒aab.
5. Answer: S⇒AB⇒Ab⇒aAb⇒aab.

Nullable variables, FIRST, and FOLLOW

Definition. A variable is nullable if it derives ε. FIRST(X) contains terminals that can begin strings derived from X, plus ε if X is nullable. FOLLOW(A) contains terminals that can immediately follow A in some sentential form; $ marks the end after the start variable.

Example. For S→AB, A→a|ε, B→b, FIRST(S)={a,b}.

Exam point. When a prefix is nullable, FIRST must continue to the next symbol; FOLLOW uses FIRST of the suffix and may inherit FOLLOW of the left-hand side.

Solved examples

Example 1 — compute FIRST. Grammar S→AB, A→a|ε, B→b|c.

1. FIRST(A)={a,ε}; FIRST(B)={b,c}.
2. S begins with A when A produces a.
3. Because A can vanish, S may also begin with B's first symbols.
4. FIRST(S)={a,b,c}; ε is not included because B is not nullable.

Example 2 — compute FOLLOW. For the grammar above, calculate FOLLOW(A) and FOLLOW(B), with S start.

1. In S→AB, B follows A, so add FIRST(B)={b,c} to FOLLOW(A).
2. B is at the right end, so FOLLOW(S) is added to FOLLOW(B).
3. FOLLOW(S) contains $.
4. FOLLOW(A)={b,c}; FOLLOW(B)={$}.

Eliminating ε-productions and unit productions

Definition. An ε-production has right side ε; a unit production has one variable on the right. Standard simplification computes nullable variables, adds alternatives that omit nullable occurrences, removes ε rules while preserving ε at the start when needed, and replaces unit chains by their non-unit consequences.

Example. If A→BC and B is nullable, add A→C before removing B→ε.

Exam point. Preserve whether the original language contains ε by using a fresh start symbol when necessary.

Solved examples

Example 1 — remove ε. Grammar S→AB, A→a|ε, B→b.

1. A is nullable.
2. For S→AB, add the alternative S→B omitting A.
3. Remove A→ε; retain A→a, and productions S→AB|B, B→b.
4. The language remains {ab,b}.

Example 2 — remove a unit rule. Grammar S→A|b, A→a|B, B→c.

1. Unit chain from S reaches A and B.
2. Non-unit alternatives reachable are a, c, and b.
3. Replace S's unit productions with S→a|b|c; replace A→B by A→c.
4. No unit production remains.

Chomsky normal form

Definition. A CFG is in CNF if every production is A→BC for variables B,C, or A→a for a terminal a; a special start rule S₀→ε may be allowed when ε belongs to the language. CNF conversion removes useless, ε, and unit rules, then isolates terminals and binarizes long right sides.

Example. A→aBC can become A→X_a D, D→BC, X_a→a.

Exam point. The start variable should not appear on a right side if the form permits a separate ε rule.

Solved examples

Example 1 — binarize. Convert the right side ABC into binary branching.

1. Introduce D with D→BC.
2. Replace A→ABC by A→AD.
3. The right side now contains exactly two variables.

Example 2 — isolate terminal. Convert A→aB to CNF form.

1. Introduce X_a→a.
2. Replace the original rule with A→X_aB.
3. Both productions satisfy CNF patterns.

Push-down automata

Definition. A PDA is a finite-state machine with a stack. A transition may inspect the input symbol (or ε), inspect/pop the stack top, and push a string; acceptance may be by final state or empty stack. Nondeterministic PDAs recognize exactly the context-free languages.

Example. For {aⁿbⁿ}, push one marker per a, then pop one per b and accept when the stack returns to its bottom marker after input ends.

Exam point. A stack is LIFO; it can match nested structure but cannot generally compare two unbounded counts separated in a way requiring two independent counters.

Solved examples

Example 1 — PDA trace. Sketch a PDA run for aaabbb with bottom symbol Z and marker A.

1. Start in qpush with Z. Read a and push A: stack AZ.
2. Read the second and third a, pushing each: AAAZ.
3. On first b, switch to qpop and pop A; repeat for remaining b symbols.
4. After three b's, stack is Z and input is exhausted.
5. Accept by final state or empty stack, according to the chosen convention.

Input consumed	State phase	Stack (top at left)
ε	push	Z
a	push	AZ
aa	push	AAZ
aaa	push	AAAZ
aaab	pop	AAZ
aaabb	pop	AZ
aaabbb	accept	Z

Example 2 — reject a count mismatch. Trace aabbb.

1. Two a's push two A markers.
2. The first two b's pop both markers.
3. The third b requires another A but sees Z.
4. No valid transition consumes the extra b; reject.

Acceptance by final state versus empty stack

Definition. For nondeterministic PDAs, acceptance by final state and by empty stack define the same class of languages, though a given PDA may need transformation. Empty-stack acceptance requires all input consumed and the stack emptied; final-state acceptance requires all input consumed and a final state reached.

Example. A PDA may use a bottom marker and move to a final state once it sees only that marker after input ends.