Context-Free Grammars Explained: Derivations, Parse Trees and Exam Traps
Learn how CFGs generate strings by deriving aaabbb and (())(), proving ambiguity with two parse trees, converting a grammar to CNF and avoiding common traps.
KnowledgeGate Team
Exam prep & CS education

A context-free grammar generates a language from a finite set of production rules. Its tuple G = (V, T, P, S) supports exact derivations for aaabbb and (())(), a two-tree ambiguity proof and a checked CNF conversion. Each conclusion follows from a derivation or a production-shape test.
1. Context-free grammar components and production rules
A context-free grammar is G = (V, T, P, S). V and T are finite sets of non-terminals and terminals, respectively, and are disjoint. P is a finite production set; S ∈ V is the start symbol. Each production is A -> α, where A ∈ V and α ∈ (V ∪ T)*.
For G1, V = {S}, T = {a, b}, P = {S -> aSb, S -> epsilon}, with start symbol S. Terminals remain in the finished string; a non-terminal is rewritten. epsilon is the length-zero string, not the empty language, which contains no strings.
G1 is the grammar; L(G1) = {a^n b^n | n >= 0} is its language. Every regular language is context-free, but this example needs matched counts that a finite automaton cannot recognise.
2. CFG derivation and parse tree for aaabbb
Each use of S -> aSb adds one a on the left and one b on the right. The counts therefore stay equal, and no b can appear before an a. For n = 3, the complete derivation is:
S => aSb => aaSbb => aaaSbbb => aaabbb
The last step applies S -> epsilon. As boundary checks, n = 0 produces epsilon, while n = 2 produces aabb. The string aabbb fails because its counts differ. The string abab fails because it breaks the required terminal order.
A leftmost derivation always rewrites the leftmost non-terminal. A rightmost derivation rewrites the rightmost one. Every intermediate form above contains only one non-terminal, so both choices coincide here. They do not coincide for every CFG.
The matching parse tree uses three recursive rewrites and then the epsilon rewrite. Its yield is the terminal leaves read from left to right. The leaves are a, a, a, epsilon, b, b, b, so the terminal yield, with epsilon contributing no symbol, is aaabbb.

3. Context-free grammar design for balanced parentheses
For balanced parentheses, use G2: S -> (S)S | epsilon. The first S on the right permits nesting inside one matched pair. The second permits another balanced block after that pair. Together, the rules generate every balanced-parentheses string, including epsilon.
Always rewriting the leftmost non-terminal gives this full derivation of (())():
S => (S)S => ((S)S)S => (()S)S => (())S => (())(S)S => (())()S => (())()
Transitions 1, 2 and 5 use S -> (S)S. Transitions 3, 4, 6 and 7 use S -> epsilon. No S disappears without a production.
The language has a useful invariant. In every prefix, the number of ( symbols is at least the number of ) symbols, and a completed string has equal counts. (() is rejected because its final counts are two openings and one closing. ())( is rejected earlier because the prefix ()) has one opening and two closings.
4. Ambiguous CFGs produce two parse trees for one string
Take G3: E -> E+E | E*E | id and the string id+id*id. It has these two leftmost derivations:
E => E+E => id+E => id+E*E => id+id*E => id+id*id, grouped asid+(id*id).E => E*E => E+E*E => id+E*E => id+id*E => id+id*id, grouped as(id+id)*id.
Two distinct parse trees, or equivalently two distinct leftmost derivations, for the same terminal string make this grammar ambiguous. That result concerns this grammar, not whether the language is inherently ambiguous. Ambiguous Grammars, Precedence and Associativity for GATE explains the distinction between grammar ambiguity and inherent ambiguity.
One repair for the intended precedence is E -> E+T | T, T -> T*F | F, F -> id | (E). Multiplication is confined to the T layer, so * binds more tightly than +. Removing ambiguity does not have one mechanical solution for every grammar.

5. Chomsky Normal Form conversion with a checked derivation
Start with G4: S -> aSb | ab, which generates {a^n b^n | n >= 1}. CNF uses A -> BC for two non-terminals, or A -> a for one terminal. Some conventions permit a start-symbol epsilon rule when the language contains epsilon; L(G4) does not.
Introduce A -> a, B -> b and C -> SB. Replace the original rules with S -> AC | AB. Since S occurs on the right in C -> SB, add the fresh start symbol S0 and set S0 -> AC | AB.
Check every rule by shape. S0 -> AC, S0 -> AB, S -> AC, S -> AB and C -> SB are two-non-terminal rules. A -> a and B -> b are terminal rules.
The converted grammar still derives aabb completely:
S0 => AC => ASB => AABB => aABB => aaBB => aabB => aabb
The steps use C -> SB, S -> AB, A -> a twice and B -> b twice. CNF changes the grammar's form, not its non-empty strings.
6. Context-free grammars and pushdown automata describe the same language class
CFGs generate context-free languages through recursive productions. Pushdown automata recognise the same class with finite control plus one stack. Context-Free Grammars and PDAs owns CFG-PDA conversions, acceptance modes, GNF and the pumping lemma; the detailed treatment here is derivations, ambiguity and CNF conversion.
The string aaabbb makes the stack memory concrete. Starting with bottom marker Z0, a PDA pushes one X per a, so its stack changes as Z0 -> XZ0 -> XXZ0 -> XXXZ0. It then pops one X per b: XXXZ0 -> XXZ0 -> XZ0 -> Z0. The input is consumed with only Z0 left, so the matched-count check succeeds.
A finite automaton lacks an unbounded stack, so it cannot retain arbitrary n for comparison with later b symbols.
7. Context-free grammar exam traps and practice checks
Keep these distinct:
epsilonis a string; the empty language is a set with no strings.A grammar is a rule system; its language is the generated set.
Left recursion does not prove ambiguity.
An ambiguous grammar does not prove its language inherently ambiguous.
A CFG may generate a regular language.
Test them quickly:
S -> aSb | epsiloncannot generateabab, because everyamust precede everyb.A -> aBis not CNF, because it mixes a terminal and a non-terminal.G3is ambiguous forid+id*id, because the two derivations above use different groupings.G4does not generateepsilon, because its shortest derivation isS => ab.
Use the 60+ set to practise the distinctions above.Context-Free Grammar MCQs: 12 Solved CFG Questions.
8. Context-free grammars in the short version
Recall: identify V, T, P, S; state the language invariant; derive the requested string without skipping rewrites; read the parse-tree yield; prove ambiguity with two structures; test every normal-form production by shape. Reproduce aaabbb, (())(), both trees for id+id*id and the CNF derivation of aabb from memory.
For a structured route through Theory of Computation, consider GATE Guidance by Sanchit Sir. The GATE CS Exam Preparation category places it within the wider study path.
Keep learning
Context-Free Grammars and Pushdown Automata: CFGs, PDAs, and a worked example
Context-free grammars and pushdown automata explained: derivations, ambiguity, CNF and GNF, PDA acceptance modes, the pumping lemma, and a worked example.
Context-Free Grammar MCQs: 12 Solved CFG Questions
Solve 12 previous-year CFG questions from GATE, UGC NET and ISRO papers by deriving the language, testing counterexamples and applying standard grammar transformations. Each answer gives the shortest useful reasoning.
Context-Free Grammar MCQs: 11 solved questions on CFG, CFL and PDA
Context-free grammar solved MCQs with explanations: 11 GATE PYQs on CFGs, the Chomsky hierarchy, CFL closure properties, pushdown automata and decidability.
Backus-Naur Form (BNF) Explained: Grammar Rules, Worked Derivations and Exam Traps
Learn to read BNF as a grammar, not as punctuation. Follow complete derivations, compare ambiguous parses, and see how recursion affects parsing.





