3.1CFG, derivations and parse trees
The idea
A context-free grammar generates strings by repeatedly rewriting variables; a derivation is that sequence of rewrites.
Think of it like this: A recipe where every dish is built from smaller dishes until you reach raw ingredients.
Why it exists
CFGs describe nested structure (brackets, expressions) that finite automata cannot.
How it works
- Start with S and replace a variable by a rule's right side.
- Leftmost: always rewrite the leftmost variable. Rightmost: the rightmost.
- A parse tree records which rule was applied where.
- One tree ⇔ one leftmost derivation ⇔ one rightmost derivation.
Worked example: S → aSb | ab
S ⇒ aSb ⇒ aaSbb ⇒ aaabbb: the language is {aⁿbⁿ : n ≥ 1}.
Now play with it
- →Flip between the leftmost and rightmost tabs and compare which variable is rewritten.
Sstart (grammar S → aSb | ab)aSbS → aSbaaSbbS → aSb (leftmost variable S)aaabbbS → ab
A leftmost derivation rewrites the leftmost variable every time. Three steps give the string aaabbb.
Check yourself
The number of leftmost derivations of a string equals
Exam notes (the dense version)
G = (V, Σ, P, S) with rules A → α. A derivation rewrites S step by step; leftmost / rightmost always expands the leftmost / rightmost variable. Each parse tree corresponds to exactly one leftmost derivation.
Previous year questions: Context-Free Grammars & Languages (13)
PYQs are grouped by topic, so this is the full set for Context-Free Grammars & Languages; try the ones that match this subtopic. Open all 13 on the topic page.