Grammar and CFG Mistakes for GATE: 7 Traps and How to Fix Them

CFG questions are often lost not because the grammar is long, but because one symbol, one nullable production, or one unsupported ambiguity claim changes the answer. The safest response is a fixed audit. These seven errors use small grammars you can reproduce under exam pressure and cover classification, generated languages, derivations and parse trees, ambiguity, left-recursion removal, LL(1) checks, and normal-form conversion.

1. Mistake 1: Classifying a Grammar from the RHS Alone

Students often classify a grammar from its right-hand side without first checking the left-hand side.

For S -> aSb | ε, every production has one non-terminal, S, on the left, so the grammar is context-free. It is not regular because the variable in aSb is trapped between terminals. In contrast, AB -> a is not context-free because its left side has two variables.

Inspect every LHS first, then test the RHS restrictions. Each recursive step in S -> aSb | ε adds one a and one b, giving {a^n b^n | n >= 0}. Only then should you place it in the Chomsky hierarchy.

2. Mistake 2: Guessing the Language from Two Sample Strings

Seeing ab and aabb does not establish a language. Check the base case and what each production preserves.

For S -> aSb | ε:

• S => ε

• S => aSb => ab

• S => aSb => aaSbb => aabb

• S => aSb => aaSbb => aaaSbbb => aaabbb

The grammar accepts ε, ab, aabb, and aaabbb, but rejects abab, aab, and abb. Every recursive step puts one a on the left and one b on the right. Thus all as precede all bs and their counts are equal. State both this invariant and the construction in your answer.

3. Mistake 3: Treating Leftmost and Rightmost Derivations as Different Parse Trees

Different derivation orders do not prove different parse trees. With S -> AB, A -> aA | a, and B -> bB | b, the string aabb has this leftmost derivation:

S => AB => aAB => aaB => aabB => aabb

Its rightmost derivation is:

S => AB => AbB => Abb => aAbb => aabb

Only the expansion order differs. In both cases, root S has children A and B; A yields aa, while B yields bb. Compare parent-child relationships, not the order of sentential forms.

4. Mistake 4: Declaring Ambiguity Without Producing Two Trees

Multiple available productions do not by themselves prove ambiguity. For E -> E+E | E*E | id, use id+id*id.

One leftmost derivation is:

E => E+E => id+E => id+E*E => id+id*E => id+id*id

It represents id+(id*id). A second is:

E => E*E => E+E*E => id+E*E => id+id*E => id+id*id

It represents (id+id)*id. The roots use different productions, so the trees differ structurally. This proves that the grammar is ambiguous, not that its language is inherently ambiguous.

5. Mistake 5: Removing Left Recursion but Changing the Language

A -> Aa | b generates {ba^n | n >= 0}. Its first four strings are b, ba, baa, and baaa. The correct rewrite is:

• A -> bA'

• A' -> aA' | ε

Check the result. Taking A' -> ε gives b; applying A' -> aA' one, two, or three times before ε gives ba, baa, or baaa.

Without ε, A' cannot terminate. With only A' -> a | ε, the grammar loses baa, baaa, and every longer string. Regenerate at least four short strings from both grammars after the transformation.

6. Mistake 6: Taking FIRST of One Symbol Instead of the Whole RHS

Consider S -> Aa | b and A -> b | ε:

• FIRST(A) = {b, ε}

• FOLLOW(S) = {$}

• FOLLOW(A) = {a}

Because A is nullable, a also contributes, so FIRST(Aa) = {a, b}, not {b, ε}. The prediction sets are:

• PREDICT(S -> Aa) = {a, b}

• PREDICT(S -> b) = {b}

• PREDICT(A -> b) = {b}

• PREDICT(A -> ε) = {a}

The productions for S overlap on {b}, so the grammar is not LL(1). With lookahead b, a parser cannot choose between ba through S -> Aa and b through S -> b.

Compute FIRST for the complete RHS, remove ε, add FOLLOW only when that RHS is nullable, and test prediction sets pairwise.

7. Mistake 7: Stopping Halfway Through CNF Conversion

Start with S -> aBC | b, B -> b, and C -> c. Replacing only the first terminal gives S -> T_aBC, which still has three variables. Writing S -> aX mixes a terminal and a variable.

A valid CNF rewrite is:

• S -> T_aX | b

• T_a -> a

• X -> BC

• B -> b

• C -> c

The first branch gives S => T_aX => aX => aBC => abC => abc; the second gives S => b. The language stays {abc, b}, and every rule has two variables or one terminal on the RHS.

Remove nullable, unit, and useless productions where needed; isolate terminals in mixed RHSs; then split RHSs longer than two. Practise a full CNF and GNF conversion line by line.

8. The 60-Second CFG Error Audit Before You Lock an Answer

Before choosing an option:

1. Inspect every LHS before classifying the grammar.

2. Test ε and at least three short strings before naming the language.

3. Separate derivation order from parse-tree structure.

4. Demand one string and two trees before claiming ambiguity.

5. Regenerate b, ba, baa, and baaa after removing left recursion.

6. Compute FIRST of the complete RHS and compare prediction sets.

7. Check every CNF production against the permitted forms.

Use the Compiler Design hub for the wider sequence. Rebuild uncertain methods with the Compiler Design course, then apply the audit under timed conditions with the GATE Test Series.