Grammar in Theory of Computation: Complete Guide with Worked Examples

"Which type of grammar is this?" looks easy until productions mix directions or a short string has extra parse trees. Machines recognise languages; grammars generate them. A grammar is judged entirely by the shape of its productions: that shape fixes its Chomsky type, the machine that accepts the language it generates, and whether one string can carry two parse trees.

What a grammar is and the language it generates

A grammar is a four-tuple G = (V, T, P, S):

• V is the set of variables, also called nonterminals.

• T is the set of terminals.

• P is the set of productions.

• S is the start symbol.

Exam questions use capitals for nonterminals, lowercase letters for terminals, and ε for the empty string. Consider G1: S -> aSb | ab.

It derives aaabbb in three production steps:

S => aSb => aaSbb => aaabbb

Thus L(G1) = {a^n b^n | n >= 1}. In general, L(G) contains all terminal-only strings derivable from S. GATE switches freely between generators and recognisers.

The Chomsky hierarchy by production shape

Check every production, then name the most restrictive type that fits them all. Chomsky Hierarchy for GATE works that inspection through four boundary grammars, one per type.

The strict containment is Type 3 inside Type 2 inside Type 1 inside Type 0.

1. G_a: S -> aS | b is right-linear, hence Type 3. It generates a*b.

2. G1 has one nonterminal on each left side, hence Type 2. It is not Type 3 because a^n b^n needs unbounded matching, which no fixed set of states can track.

3. G_c has S -> abc | aSBc, cB -> Bc, and bB -> bb. Its left sides can contain several symbols, but no rule contracts the string. It is Type 1 and generates {a^n b^n c^n | n >= 1}.

For n = 2, the complete derivation is:

S => aSBc => aabcBc => aabBcc => aabbcc

This takes four steps, using cB -> Bc and then bB -> bb at the end.

Regular grammars and finite automata

Take G2: S -> aS | bS | aA; A -> b. It generates all strings over {a, b} ending in ab, written (a+b)*ab. For an NFA, make one state per nonterminal plus a final state F. Convert B -> xC into B -x-> C, and B -> x into B -x-> F.

The states are S, A, and F; transitions are S -a-> S, S -b-> S, S -a-> A, and A -b-> F. Two a moves leave S, so this valid machine is nondeterministic. Subset construction converts it to an equivalent DFA, worked through in the DFA versus NFA guide.

In reverse, p -x-> q becomes p -> xq, and each final state q receives q -> ε.

Do not mix directions. G3: S -> aA | ε; A -> Sb looks linear but generates {a^n b^n | n >= 0}. Type 3 must stay entirely right-linear or left-linear.

Derivations, parse trees, and ambiguity

A sentential form is an intermediate derivation string. Leftmost and rightmost derivations expand the corresponding nonterminal first. Each parse tree fixes exactly one of each.

G4: S -> aS | Sa | a generates a^n for n >= 1, but is ambiguous. For aa, the root can use S -> aS or S -> Sa, with the remaining S producing a. These are two trees.

For aaa, root rule aS contributes two trees and Sa contributes two, totalling 2 + 2 = 4. If t(n) counts trees for a^n, then t(1) = 1 and t(n) = 2t(n-1), so t(n) = 2^(n-1).

G5: S -> aS | a generates the same language unambiguously. Ambiguity belongs to a grammar, not automatically to its language. CFG ambiguity is undecidable in general, but two trees for one string settle a small example.

Chomsky and Greibach normal forms

In Chomsky Normal Form, every production is A -> BC or A -> a. Convert G1 to:

A -> a

B -> b

X -> SB

S -> AX | AB

For aabb, a complete derivation is:

S => AX => aX => aSB => aABB => aaBB => aabB => aabb

The seven steps match 2n - 1 for n = 4. In general, CNF needs n - 1 binary steps and n terminal steps. Thus length-6 aaabbb takes 2(6) - 1 = 11 steps in CNF, but only three in the original G1. Never use this count outside CNF.

In Greibach Normal Form, each right side starts with a terminal followed by variables. Here S -> aSB | aB; B -> b works. Normal forms support fixed-shape proofs and CYK. FIRST, FOLLOW, left recursion, and LL or LR parsing are Compiler Design topics that build on these forms.

Traps that cost marks

• Choosing Type 2 for a regular grammar: By containment it fits, but the expected most restrictive class is Type 3.

• Treating mixed linear rules as regular: G3 shows that mixing left and right forms can generate the non-regular language a^n b^n.

• Ignoring contraction in Type 1: A shorter right side breaks the rule, except S -> ε when S never appears on a right side.

• Confusing trees and derivations: aa under G4 has two trees and two derivations because each form has one nonterminal. With several nonterminals, expansion orders can create more unrestricted derivations than trees.

• Using 2n - 1 outside CNF: aaabbb takes three steps in G1 and 11 only after the CNF conversion.

• Reversing containment: Every regular language is context-free, not the other way around.

How GATE and interviews test grammar

Grammar and the Chomsky hierarchy sit within Theory of Computation and connect to Compiler Design. Check the conducting institute's official GATE 2026 site for the current syllabus and brochure, not remembered marks or rules.

Recent GATE papers have used five shapes: classify a grammar, identify L(G), count trees or CNF steps, convert between a regular grammar and finite automaton, or select a grammar for a language. KnowledgeGate has around 90 Grammar questions within around 1,000 Theory of Computation questions, plus around 250 on pushdown automata and CFGs. Use the Theory of Computation Context-Free Grammars MCQs for solved practice.

Interviews ask why regular expressions cannot handle arbitrary nesting, how to write G1, or how to classify a small language. A finite automaton has finitely many states and no stack, so it cannot match an unbounded number of opening symbols against closing ones, which is why nesting needs a context-free grammar and a pushdown automaton.

The short version and the next step

• G = (V, T, P, S), and L(G) contains every terminal string derivable from S.

• The strict hierarchy runs Type 3 inside Type 2 inside Type 1 inside Type 0.

• Regular grammars convert directly to finite automata, but mixed left and right linearity is unsafe.

• Two trees for aa prove G4 ambiguous; aaa has four.

• In CNF, a length-n string takes exactly 2n - 1 derivation steps.

Learn the subject in sequence with GATE Guidance by Sanchit Sir, then practise classification and step counting against the clock. The wider GATE CS Exam Preparation Courses and Test Series category connects this topic to the rest of the preparation plan.