Chomsky hierarchy questions mix three ideas: restrictions on grammar rules, families of languages and the machines that recognise them. The type numbers make this harder because expressive power increases as the numbers fall from Type 3 to Type 0.
Ten previous-year questions follow, from UGC NET, ISRO, GATE and Bihar STET papers between 2007 and 2025. They move from ordering the four language classes and matching each to its machine, through classifying a concrete grammar, to placing recursive languages in the chain and deciding what disambiguation does to a language. Commit to an option before reading its explanation, then check the trap named at the end of each answer. The same four rows sit behind most automata questions in GATE computer science and in UGC NET Paper 2.
1. Build one hierarchy map before solving the set
Type | Grammar or language | Recognising machine | Rule cue | Concrete witness |
|---|---|---|---|---|
Type 3 | Regular | Finite automaton |
|
|
Type 2 | Context-free | Pushdown automaton |
|
|
Type 1 | Context-sensitive | Linear bounded automaton | Non-contracting: |
|
Type 0 | Unrestricted or recursively enumerable | Turing machine | No Type 1 to Type 3 production restriction |
|
Use two rules. First, expressive power rises in the order Type 3, Type 2, Type 1, Type 0. Second, a language belongs to every broader class above its tightest classification. Therefore, the "highest type number" means the most restrictive valid type.
Consider S -> Aa, A -> Ba, B -> abc. Its complete derivation is S => Aa => Baa => abcaa, and that is the only derivation available, so the grammar generates the single string abcaa. Every rule either puts a non-terminal at the left end of the right-hand side or uses terminals alone, which is the left-linear form, so the grammar is regular. If your course insists on one terminal per rule, keep the same direction and split B -> abc as B -> Xc, X -> Yb, Y -> a. Swapping in a right-linear rule such as B -> aC would break the form, because a grammar that mixes both directions is no longer regular by definition. The highest valid type number is therefore Type 3.
2. Questions 1-2: order the hierarchy and match each machine
Question 1 (UGC NET 2024)
Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy:
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted Grammars
Choose the correct answer from the options given below:
(a) (C), (A), (B), (D)
(b) (C), (A), (D), (B)
(c) (A), (C), (B), (D)
(d) (A), (D), (B), (C)
Answer: (a) (C), (A), (B), (D).
C is regular, A context-free, B context-sensitive and D unrestricted. Ascending expressive power is therefore C, A, B, D. The witnesses (ab)*, {a^n b^n}, and {a^n b^n c^n} make each jump tangible. Do not confuse option labels with Chomsky type numbers.
Question 2 (UGC NET 2022)
Match List I with List II:
List I: (A) Type 0, (B) Type 1, (C) Type 2, (D) Type 3
List II: (I) Finite automata, (II) Turing machine, (III) Linear bounded automata, (IV) Pushdown automata
Choose the correct answer from the options given below:
(a) (A)−(III),(B)−(IV),(C)−(II),(D)−(I)
(b) (A)−(II),(B)−(III),(C)−(IV),(D)−(I)
(c) (A)−(III),(B)−(IV),(C)−(I),(D)−(II)
(d) (A)−(II),(B)−(III),(C)−(II),(D)−(IV)
Answer: (b) (A)−(II),(B)−(III),(C)−(IV),(D)−(I).
From the hierarchy map, Type 0 uses a Turing machine, Type 1 a linear bounded automaton, Type 2 a pushdown automaton and Type 3 a finite automaton. That gives A-II, B-III, C-IV, D-I. The trap is reading the two lists in parallel, which pairs Type 0 with finite automata and runs the mapping backwards. Option (d) can be struck on sight: it uses (II) twice and leaves (I) unused.
3. Questions 3-4: recognise regular and context-free rule shapes
Question 3 (UGC NET 2017)
Finite state machine can recognize language generated by __________.
(a) Only context free grammar
(b) Only context sensitive grammar
(c) Only regular grammar
(d) any unambiguous grammar
Answer: (c) Only regular grammar.
Regular grammars, regular expressions and finite automata describe the same class. A machine for (ab)* only tracks whether it expects a or b, while {a^n b^n | n >= 0} needs an unbounded count. Ambiguity concerns parse trees, not finite-state recognition. Practise with Finite Automata MCQs: 10 Solved DFA and NFA (GATE).
Question 4 (UGC NET 2015)
If all the production rules have single non-terminal symbol on the left side, the grammar defined is :
(a) Context free grammar
(b) Context sensitive grammar
(c) Unrestricted grammar
(d) Phase grammar
Answer: (a) Context free grammar.
A context-free production has the form A -> alpha: one non-terminal on the left and any string on the right. For S -> aSb | epsilon, derive S => aSb => aaSbb => aabb. A regular grammar is more restricted. Review Context-Free Grammars and Pushdown Automata.
4. Questions 5-6: identify Type 1, then classify a concrete grammar
Question 5 (Bihar STET 2025)
Which of the following is type 1 language or Type 1 grammar?
(a) Regular grammar
(b) Context Free Grammar
(c) Context Sensitive Grammar
(d) Recursively Enumerable
Answer: (c) Context Sensitive Grammar.
The lookup is Type 3 regular, Type 2 context-free, Type 1 context-sensitive and Type 0 unrestricted. Type 1 rules are non-contracting, apart from the restricted start-symbol exception for epsilon. In aAb -> aaBb, context surrounds A, and length grows from three symbols to four. The trap is treating a low type number as a small class: Type 1 is the second largest of the four, and option (d), recursively enumerable, is Type 0.
Question 6 (ISRO 2016)
What is the highest type number that can be assigned to the following grammar?
S → Aa
A → Ba
B → abc
(a) Type 0
(b) Type 1
(c) Type 2
(d) Type 3
Answer: (d) Type 3.
Apply all rules: S => Aa => Baa => abcaa, the only derivation, so the language is the single string abcaa. Every rule is left-linear: S -> Aa and A -> Ba put the non-terminal at the left end, and B -> abc is terminals alone. Types 2, 1 and 0 contain it too, which makes those options true but looser. The trap is answering Type 2 because the right-hand sides carry more than one terminal.
5. Question 7: place recursive languages inside the broader chain
Question 7 (UGC NET 2014)
Given the recursively enumerable language (LRE), the context sensitive language (LCS), the recursive language (LREC), the context free language (LCF) and deterministic context free language (LDCF). The relationship between these families is given by
(a) LCF ⊆ LDCF ⊆ LCS ⊆ LRE ⊆ LREC
(b) LCF ⊆ LDCF ⊆ LCS ⊆ LREC ⊆ LRE
(c) LDCF ⊆ LCF ⊆ LCS ⊆ LRE ⊆ LREC
(d) LDCF ⊆ LCF ⊆ LCS ⊆ LREC ⊆ LRE
Answer: (d) LDCF ⊆ LCF ⊆ LCS ⊆ LREC ⊆ LRE.
Check each link. Every deterministic CFL is a CFL, and every CFL is context-sensitive. A fixed input gives a context-sensitive machine a finite bounded configuration space, so membership is decidable. Every decider is a recogniser, placing recursive languages inside recursively enumerable languages. The traps reverse LDCF ⊆ LCF or LREC ⊆ LRE.
6. Questions 8-10: generate a string, detect ambiguity and preserve the language
Question 8 (ISRO 2016)
S → aSa ∣ bSb ∣ a ∣ b. The language generated by the above grammar over the alphabet {a, b} is the set of:
(a) all palindromes
(b) all odd length palindromes
(c) strings that begin and end with the same symbol
(d) all even length palindromes
Answer: (b) all odd length palindromes.
The bases a and b have length one. Each recursive rule adds the same symbol at both ends, preserving palindromes and adding two to the length. Thus S => aSa => abSba => ababa, of length five. Without epsilon or a two-symbol base, no even-length palindrome can be generated.
Question 9 (ISRO 2020)
A given grammar is called ambiguous if:
(a) two or more productions have the same non-terminal on the left hand side
(b) a derivation tree has more than one associated sentence
(c) there is a sentence with more than one derivation tree corresponding to it
(d) brackets are not present in the grammar
Answer: (c) there is a sentence with more than one derivation tree corresponding to it.
Ambiguity means one terminal string has two parse trees. With E -> E+E | E*E | id, id+id*id can mean (id+id)*id or id+(id*id). Shared left sides do not prove ambiguity, and missing brackets are not its definition.
Question 10 (GATE IT 2007)
Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?
(a) L (D) ⊂ L (G)
(b) L (D) ⊃ L (G)
(c) L (D) = L (G)
(d) L (D) is empty
Answer: (c) L (D) = L (G).
Disambiguation changes parse structure, not language membership. A precedence-aware grammar can force id+id*id to parse only as id+(id*id) while preserving the same set of expression strings. The trap is reading that equality as a general guarantee: some context-free languages are inherently ambiguous and admit no unambiguous grammar, so a disambiguated D does not always exist. Where it does, it generates exactly L(G).
7. Score by misconception and choose the next practice step
Skill to review | Questions |
|---|---|
Hierarchy order and machine mapping | 1-2 |
Regular versus context-free cues | 3-4 |
Type 1 and tightest grammar classification | 5-6 |
Decidable versus recognisable | 7 |
Generation and ambiguity | 8-10 |
Retest the step you missed. For Questions 1 or 2, redraw the boxes and machines. For Question 6, repeat S => Aa => Baa => abcaa. For Question 7, write LDCF ⊆ LCF ⊆ LCS ⊆ LREC ⊆ LRE. For Question 8, derive ababa. For Questions 9 or 10, draw both trees for id+id*id, then apply precedence.
When the four rows are automatic, move up a level with Context-Free Grammar MCQs: 11 Solved CFG, CFL, PDA, which applies these classification rules to CFG, CFL and pushdown-automata questions. For the whole automata sequence taught in order, GATE Guidance by Sanchit Sir and NTA-UGC-NET Paper - 2 both carry it. Reproduce the hierarchy, machine mapping and short derivations without looking; that is what keeps the method reliable when the notation changes.
The short version
First identify whether an option describes a grammar rule, a language class or a machine. Then walk Type 3, Type 2, Type 1, Type 0, widening at each step: regular inside context-free inside context-sensitive inside recursively enumerable, recognised in that same order by finite automaton, pushdown automaton, linear bounded automaton and Turing machine. Recursive languages sit between context-sensitive and recursively enumerable, and disambiguating a grammar never changes the language it generates.
