Formal Grammar and Chomsky Hierarchy for GATE: Worked Derivations and Classification

The four grammar types are easy to memorise as names, but classification fails when you must inspect a production's left side, right side and length together. Three habits fix that: derive before claiming membership, read the production form before naming the type, and settle ambiguity with two parse trees rather than two strings. All three start from one tuple, G=(V,T,P,S).

Formal grammar begins with four objects, not four Chomsky types

A formal grammar is a tuple G=(V,T,P,S). V is a finite set of variables or nonterminals, T is a finite terminal alphabet disjoint from V, P is a finite set of productions, and S in V is the start symbol. A grammar generates strings; an automaton recognises them, and knowing which side a question sits on decides half of it. The wider Theory of Computation route sits under GATE CS Exam Preparation.

Use G1=({S},{a,b},{S -> aSb | epsilon},S) as the basic example. S is the only nonterminal, a and b are terminals, S -> aSb is recursive, and S -> epsilon stops the derivation. Here epsilon is the empty string of length 0, not a terminal printed in the result.

A sentential form may still contain a nonterminal, so aaSbb is one. A sentence contains only terminals, so aabb is a sentence. The language is L(G1)={a^n b^n | n>=0}: it contains epsilon, ab, aabb and aaabbb, but not aab, abab or ba.

Grammar derivation worked example: generate aaabbb

Apply the recursive rule three times, then stop:

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

The first three steps use S -> aSb; the last uses S -> epsilon. The result has three a symbols followed by three b symbols, so it is the n=3 member of a^n b^n.

The parse tree has root S and three nested S nodes. Each of the first three expands to left child a, middle child S, and right child b; the deepest S becomes epsilon. Its leaves read a a a epsilon b b b, which becomes aaabbb after omitting epsilon.

For membership, S => aSb => aaSbb => aabb proves that aabb is generated. abab cannot be generated because every recursive step adds one a at the far left and one b at the far right. Thus all a symbols must precede all b symbols. Since each sentential form here contains only one nonterminal, leftmost and rightmost derivations make the same choice.

Chomsky hierarchy connects restrictions to machine power

The hierarchy classifies grammars by production form and the resulting language families by expressive power.

As language families, regular is contained in context-free, which is contained in context-sensitive, which is contained in recursively enumerable. Classification questions usually want the most restrictive, or tightest, satisfied type. A finite automaton has finite-state memory, a pushdown automaton adds one stack, a linear-bounded automaton uses tape bounded by input length, and a Turing machine has unrestricted tape in the model. For Type 3 recogniser details, continue with Finite Automata: DFA vs NFA and Subset Construction.

Chomsky grammar classification uses a strict checklist

Test Type 3 form and consistent linear orientation first. If that fails, ask whether every left side is one nonterminal for Type 2. Next test noncontraction for Type 1; use Type 0 only after those checks fail. If a question defines a special convention for epsilon, state and follow it.

1. R=({S,A},{0,1},{S -> 0A | 1, A -> 1A | 0},S) is Type 3 because every production is right-linear. Samples are S => 1, S => 0A => 00, and S => 0A => 01A => 010. Type 3 is tightest even though the language belongs to every enclosing family.

2. G1 is Type 2. Every left side is the single nonterminal S, but S -> aSb is not right-linear because its nonterminal lies between terminals. Its language {a^n b^n | n>=0} is context-free and not regular.

3. Let C=({S,B,C},{a,b,c},P,S), where P={S -> aSBC | aBC, CB -> BC, aB -> ab, bB -> bb, bC -> bc, cC -> cc}. It is Type 1: every rule preserves or increases length, while multi-symbol left sides rule out Type 2. For n=2:

S => aSBC => aaBCBC => aaBBCC => aabBCC => aabbCC => aabbcC => aabbcc

The rules used are, in order, S -> aSBC, S -> aBC, CB -> BC, aB -> ab, bB -> bb, bC -> bc, and cC -> cc.

1. U=({S,A,B},{a},{S -> AB, AB -> A, A -> a},S) is Type 0 because AB -> A contracts length from 2 to 1 and has a multi-symbol left side. Yet S => AB => A => a, so L(U)={a}, a regular language. The presented grammar's syntactic type and the smallest family containing its language are different questions.

Ambiguous grammar worked example: two parses for id+id*id

A grammar is ambiguous if at least one generated string has two distinct parse trees. Equivalently, that string has two distinct leftmost derivations or two distinct rightmost derivations. A string by itself is not called an ambiguous grammar.

For E -> E+E | E*E | id, the same string has two leftmost derivations:

1. E => E+E => id+E => id+E*E => id+id*E => id+id*id, grouping it as id+(id*id) with + at the root.

2. E => E*E => E+E*E => id+E*E => id+id*E => id+id*id, grouping it as (id+id)*id with * at the root.

Repair precedence and left associativity with E -> E+T | T, T -> T*F | F, and F -> id. Its unique leftmost derivation is E => E+T => T+T => F+T => id+T => id+T*F => id+F*F => id+id*F => id+id*id. Multiplication now sits below addition in the parse tree. Inherent ambiguity, where no unambiguous grammar exists at all, continues in Context-Free Grammars and PDAs: CNF, GNF, Pumping Lemma.

Formal grammar questions reduce to five repeatable checks

Five confusions come up again and again, and each one has a mechanical test that settles it.

1. For S -> aSb | epsilon, aabb needs two recursive steps and one stopping step. aaabb is impossible because the counts differ.

2. AB -> aB cannot be Type 2 because the left side has two symbols. Equal side lengths do not violate Type 1.

3. A -> aB | a is right-linear; A -> Ba | a is left-linear. Follow the permitted orientation consistently rather than mixing forms.

4. S -> aSb | epsilon is Type 2, not Type 3, despite its regular-looking terminal additions.

5. Two final strings do not prove ambiguity. One fixed string needs two distinct parse structures, as id+id*id does above.

On scratch paper, circle each left side, compare side lengths, mark the nonterminal position, choose the tightest satisfied row, and verify ambiguity with two full derivations. The GATE Test Series puts that routine under a clock, where it either holds or falls apart.

Formal grammar and Chomsky hierarchy in the short version

Write G=(V,T,P,S). Separate terminals from variables. Derive before guessing membership. Test Type 3 first, then the single-nonterminal left side of Type 2, then Type 1 noncontraction. Prove ambiguity by deriving the same string twice.

The results to remember are S => aSb => aaSbb => aaaSbbb => aaabbb; R: Type 3, G1: Type 2, C: Type 1, U: Type 0; and id+(id*id) versus (id+id)*id. If you want formal languages sequenced with the rest of GATE CS, GATE Guidance by Sanchit Sir is the next step.

Self-test: classify H=({S,A},{a,b},{S -> aA | b, A -> aA | b},S) and generate a length-3 string.

Answer: Type 3; S => aA => aaA => aab generates aab.