Grammar and CFG Formula Sheet: Rules, Worked Example and GATE Revision Notes

Follow problem-solving order: identify the grammar, describe its language, transform it, compute parser sets, then audit. Use the Compiler Design Blog for the wider sequence. One grammar supports every step.

CFG notation and derivation rules to recall first

A context-free grammar G = (V, Sigma, P, S) has finite variables V, terminal alphabet Sigma, productions P, and start S in V, with V intersection Sigma = empty set.

Its literal test is A -> alpha, where A in V and alpha in (V union Sigma)*. Check that every left side is one variable before reading the right side.

epsilon is the empty string of length zero, not an input terminal. Leftmost and rightmost derivations change expansion order, but can describe the same parent-child parse tree. See Grammar in Theory of Computation: Types, Trees and CNF for a fuller refresher.

Chomsky hierarchy and the fast classification test

The hierarchy is Regular subset CFL subset CSL subset RE. Moving right gives more expressive power, not a claim that one grammar uses all of it.

S -> aSb | epsilon is context-free but not regular because S lies between terminals. AB -> a is not context-free because its left side has two variables. A -> aB | b is right-linear, hence regular. Inspect every left side first, then apply the stricter right-side rule.

Nullable, useful, ambiguous and simplified properties

Nullable(A) means A =>* epsilon. A variable is generating if A =>* w for some w in Sigma*, reachable if S =>* alpha A beta, and useful if both hold. Use nullability for epsilon removal and FIRST; use the other two properties to find useless symbols.

Simplify in this safe order:

1. Add a fresh start if the language contains epsilon and the old start occurs on a right side.

2. Remove epsilon-productions, preserving the required start epsilon.

3. Remove unit productions such as A -> B.

4. Remove non-generating and unreachable symbols.

Recheck after each phase because one removal can expose another.

A grammar is ambiguous if one terminal string has two distinct parse trees, equivalently two distinct leftmost derivations. Opposite derivation orders for one tree do not prove ambiguity, and one ambiguous grammar does not prove its language inherently ambiguous. For E -> E+E | E*E | id, id+id*id has trees id+(id*id) and (id+id)*id.

Worked CFG for aabbc: derivation, nullable, FIRST and FOLLOW

Use V={S,A,B}, Sigma={a,b,c}, start symbol S, and these productions:

S -> AB
A -> aA | epsilon
B -> bB | c

A generates a^i, while B generates b^j c. Therefore,

L(G) = {a^i b^j c | i,j >= 0}.

For i=2 and j=2, the leftmost derivation is:

S => AB => aAB => aaAB => aaB => aabB => aabbB => aabbc.

The yield is aabbc. The epsilon step removes the final A and contributes no input symbol.

Now compute nullable values directly. Nullable(A)=true because A -> epsilon. Nullable(B)=false. Hence Nullable(S)=false, since B cannot vanish.

For the first sets, FIRST(A)={a,epsilon} and FIRST(B)={b,c}. Since A is nullable, FIRST(AB) must continue into B. Thus FIRST(S)=FIRST(AB)={a,b,c}.

For follow sets, first put $ in FOLLOW(S). In S -> AB, add FIRST(B)-{epsilon}={b,c} to FOLLOW(A). Since B ends the production, add FOLLOW(S) to FOLLOW(B). The final sets are FOLLOW(S)={$}, FOLLOW(A)={b,c} and FOLLOW(B)={$}.

Left recursion, left factoring, PREDICT sets and LL(1)

Immediate left recursion

A -> A alpha1 | ... | A alpham | beta1 | ... | betan

becomes

A -> beta1 A' | ... | betan A'

A' -> alpha1 A' | ... | alpham A' | epsilon,

where no beta begins with A. Apply this before predictive top-down parsing.

Left-factor A -> alpha beta1 | alpha beta2 into A -> alpha A' and A' -> beta1 | beta2 when alternatives share a lookahead prefix. Both rewrites must preserve the language; neither proves unambiguity.

PREDICT(A -> alpha) is FIRST(alpha)-{epsilon}, plus FOLLOW(A) only if epsilon in FIRST(alpha). LL(1) requires pairwise disjoint PREDICT sets for each variable's alternatives.

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

• PREDICT(A->aA)={a} and PREDICT(A->epsilon)={b,c}

• PREDICT(B->bB)={b} and PREDICT(B->c)={c}

These sets do not collide:

CNF, GNF, BNF and CYK without name confusion

Chomsky Normal Form permits A -> BC or A -> a, plus S0 -> epsilon under the standard start-symbol conditions. Use CNF for CYK or binary parse-tree arguments. Greibach Normal Form requires A -> a alpha, where a in Sigma and alpha in V*, with controlled start epsilon when required. Use GNF when each leftmost step must expose a leading terminal.

Check this exact CNF conversion:

S -> aBC | b                 S -> T_a X | b
B -> b                       T_a -> a
C -> c                       X -> BC
                             B -> b
                             C -> c

Every converted rule produces two variables or one terminal, and both grammars generate {abc,b}. Practise the full method in CNF and GNF Conversion for GATE.

BNF uses ::= and |; EBNF adds optional [ ] and repetition { }. They are specification notations, not normal forms.

For CYK on a CNF grammar, set T[i,1]={A | A->w_i} and combine every binary split. Accept a length-n word iff S in T[1,n]. A length-5 input has 5*6/2=15 triangular cells.

How GATE can test this sheet and what to audit

IIT Guwahati's GATE 2026 CS syllabus lists "Context-free grammars and push-down automata" under Theory of Computation and "Lexical analysis, parsing, syntax-directed translation" under Compiler Design. These lines define scope, not marks, frequency or weightage.

A question can ask you to classify a grammar, infer its language, compare derivations and trees, prove ambiguity with two trees, simplify productions, remove immediate left recursion, left-factor a prefix, calculate nullable, FIRST, FOLLOW and PREDICT, detect an LL(1) collision, check CNF or GNF, or run CYK membership.

Audit every answer:

• Inspect the entire left side before classification.

• Compute FIRST of the whole right side, not only its first symbol.

• Never put epsilon in FOLLOW.

• Add FOLLOW to PREDICT only when the full right side is nullable.

• Test epsilon and several short strings after a transformation.

The five-minute CFG revision routine and next step

1. Write G=(V,Sigma,P,S) and inspect every left side.

2. Generate epsilon plus three short strings, then state the invariant.

3. Mark nullable symbols.

4. Compute FIRST left to right and FOLLOW from production context.

5. Build disjoint PREDICT sets before calling the grammar LL(1).

6. Regenerate short strings after simplification or normal-form conversion.

The short version is: classify, derive, calculate, transform, verify. KnowledgeGate offers over 100 published questions in Compiler Design > Grammar & CFG. Follow Compiler Design for parsing, Theory Of Computation / Automata Theory for formal languages, or revisit the Compiler Design Blog above.