Chomsky Hierarchy Explained: Grammar Types, Worked Classification and Exam Traps

You may remember the labels Type 0 to Type 3, yet still freeze when a production such as S -> aAB appears. Which test should come first, and when can you stop? Use a rule-by-rule method: identify the grammar components, move from the most restrictive class outwards, classify one complete grammar, and derive the exact string aaabb. The CS Fundamentals for Exams & Placements category connects the hierarchy to adjacent automata and compiler topics.

1. Formal grammar basics before the Chomsky hierarchy

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

• V is a finite set of variables, also called non-terminals.

• T is a finite set of terminals, with V and T disjoint.

• P is the set of productions.

• S is the start symbol and belongs to V.

The notation => marks one derivation step, while =>* marks zero or more steps. epsilon is the empty string. Keep grammar symbols distinct from the language they generate.

Take the warm-up grammar G0 = ({S}, {0,1}, {S -> 0S1, S -> epsilon}, S). To generate 0011, rewrite without skipping a step:

S => 0S1 => 00S11 => 0011

Each recursive step adds one 0 on the left and one 1 on the right; S -> epsilon then removes S. Thus L(G0) = {0^n 1^n | n >= 0}. The string 0011 belongs. The string 0101 does not, because all 0s must precede all 1s and the counts must match. Chomsky Hierarchy for GATE: Classify Any Grammar Fast provides four boundary-focused classification drills. The G1 example connects the same production tests with a complete derivation.

2. The Chomsky hierarchy as four nested language families

Remember the containment from the narrowest family to the broadest:

Type 3 subset Type 2 subset Type 1 subset Type 0

These are the regular, context-free, context-sensitive, and recursively enumerable language families. Moving from Type 3 towards Type 0 permits more general production forms and requires a more powerful recogniser.

These are theoretical correspondences. If a grammar satisfies several rows, report its most restrictive valid type. A right-linear Type 3 grammar also fits the Type 2 left-side condition, but its answer is Type 3.

3. Type 3 and Type 2: regular versus context-free production shapes

A right-linear Type 3 grammar uses A -> aB and A -> a, plus a start-symbol empty rule where the convention permits it. Its left-linear counterparts are A -> Ba and A -> a. Use one orientation consistently for the usual regular-grammar test.

For example, S -> 0A and A -> 1A | 1 generate 01+, meaning one 0 followed by one or more 1s. A derivation of 0111 is:

S => 0A => 01A => 011A => 0111

For Type 2, every production is A -> gamma: the left side is one variable, while gamma may contain terminals and variables, including epsilon where allowed. Thus S -> 0S1 | epsilon is context-free, but not regular because the recursive S is surrounded by terminals. Context-Free Grammars and Pushdown Automata is the next layer for connecting this class to PDA behaviour.

4. Type 1 and Type 0: non-contracting versus unrestricted rules

A Type 1 production can be written alpha A beta -> alpha gamma beta, where gamma is non-empty and the surroundings give context. The equivalent classification check is non-contraction: |RHS| >= |LHS| for every ordinary production.

In aA -> ab, A becomes b in the left context a, and length is preserved as 2 -> 2. A usual exception permits S -> epsilon when S never appears on a right-hand side. Follow any different convention stated in the question.

A Type 0 production is alpha -> beta, where alpha contains a variable and beta is unrestricted. AB -> A passes Type 0 but fails Type 1: its length changes from 2 to 1, so it contracts.

5. Worked example: classify G1 and derive aaabb

Consider the complete grammar:

G1 = ({S,A,B}, {a,b}, P, S)

where P = {S -> aAB, A -> aA, A -> a, B -> bB, B -> b}.

Start with the narrowest test. Type 3 fails because S -> aAB has two variables on the right, so it is not linear. Type 2 succeeds because every left side is one variable. The grammar is therefore Type 2. Its rules are also non-contracting, but that broader Type 1 property does not change the answer.

Now derive aaabb, naming the production used each time:

1. S => aAB using S -> aAB.

2. => aaAB using A -> aA.

3. => aaaB using A -> a.

4. => aaabB using B -> bB.

5. => aaabb using B -> b.

Reading the final leaves from left to right gives three a symbols followed by two b symbols.

A generates a^k for k >= 1, the initial a adds one, and B generates b^n for n >= 1. Hence L(G1) = {a^m b^n | m >= 2, n >= 1}. The string aab belongs through S => aAB => aaB => aab; abb does not because every result has at least two a symbols.

6. Common Chomsky hierarchy traps and fast corrections

Use each error to trigger a specific correction:

• Starting at Type 0: Almost every valid grammar then looks unrestricted, which loses the strongest classification. Start at Type 3 and stop at the first class whose conditions every rule satisfies.

• Stopping at a single-variable left side: That proves Type 2, but the grammar may still be Type 3. First inspect every right side for consistent linearity.

• Confusing orientation with length: The rule aA -> ab is non-contracting, with length 2 -> 2, but it is not context-free because its left side has two symbols. The rule S -> 0S1 is context-free, but not regular, because the variable is surrounded by terminals.

• Mixing linear orientations: Do not combine right-linear and left-linear rules and automatically label the result regular. Apply the orientation convention given in the question.

• Classifying the language instead of the displayed grammar: A badly shaped grammar may generate a language that another, more restrictive grammar can generate. Unless the question explicitly asks for the language family, classify the grammar actually shown.

7. How exams test Chomsky basics, then the short version

Common exam tasks match types with machines, ask for the strongest restriction, classify a production set, order the families, identify a rule that breaks a type, or test a derivation.

Try this rapid check:

1. S -> aA, A -> bA | b is Type 3 because all rules are right-linear.

2. S -> aSb | epsilon is Type 2 but not Type 3 because the recursive variable is surrounded.

3. AB -> A is Type 0 but not Type 1 because it contracts from length 2 to length 1.

For timed diagnosis across the syllabus, use the GATE Test Series after you can classify the examples without notes.

Apply a four-question retrieval ladder to a grammar. Are all rules consistently linear? Type 3. Does every rule have one variable on the left? Type 2. Are all ordinary rules non-contracting or context-sensitive? Type 1. Otherwise, does each left side contain a variable? Type 0.

For G1, S -> aAB defeats Type 3 and every left side is one variable, so the answer is Type 2. Continue with ZERO TO HERO for a sequenced core-CS route, or spend five minutes re-deriving aaabb and classifying the rapid-check grammars from memory.