Grammar-classification questions look like memory tests, but they are really inspection tests. One unusual production can move the whole grammar to a less restrictive class, and guessing from the language can hide that production.
The reliable method is mechanical: inspect every left-hand side, inspect every right-hand side, and report the most restrictive class that accepts all the rules. Two questions settle it, asked in a fixed order.
1. The four types and the one question you actually answer
The Chomsky hierarchy, from most restrictive to least restrictive, is:
Type 3 Regular ⊂ Type 2 Context-Free ⊂ Type 1 Context-Sensitive ⊂ Type 0 Unrestricted
The containment matters. A regular grammar also satisfies the broader context-free and unrestricted conditions. Therefore, when a question asks for the grammar's type, it normally wants the tightest class, meaning the most restrictive class that contains every production.
Start with Type 3 and test downward. If every rule passes the regular form, stop. If even one rule fails, test Type 2, then Type 1, then Type 0. Classify the grammar that is written, not merely a familiar-looking language it may generate.
2. The production-form rule for each type
Each type is defined by one restriction on production shape, and each restriction matches one machine model.
Type | Permitted production shape | Machine model |
|---|---|---|
Type 3, Regular |
| Finite automaton |
Type 2, Context-Free |
| Pushdown automaton |
Type 1, Context-Sensitive |
| Linear bounded automaton |
Type 0, Unrestricted |
| Turing machine |
For a right-linear grammar, the optional non-terminal must stay at the right end of the right-hand side. A left-linear grammar places it at the left end. Do not mix the two orientations when applying the standard Type 3 production test.
A context-free right-hand side can be any string of terminals and non-terminals, including a long string. Its defining restriction is on the left: exactly one non-terminal.
For the usual non-contracting presentation of a context-sensitive grammar, no rule may shorten the sentential form. Type 0 removes that length condition.
The flowchart tests one production at a time, but the final label must cover the complete grammar. The least restrictive rule determines the answer.
3. Worked example: four grammars, one at each boundary
Regular boundary
Consider G1 = {S→aB, B→bB, B→b}.
Every left-hand side is one non-terminal. Every right-hand side is a terminal alone or a terminal followed by one non-terminal. All rules are right-linear, so G1 is Type 3.
Starting with S→aB, repeat B→bB zero or more times and finish with B→b. The language is L(G1) = {ab^n : n ≥ 1}.
Context-free boundary
Now use G2 = {S→aB, B→bBc, B→ε}.
The production B→bBc places terminals on both sides of B. It is not right-linear or left-linear, so the grammar fails the Type 3 form. Every left-hand side is still one non-terminal, so it is Type 2.
After n recursive applications and one B→ε, it generates L(G2) = {ab^n c^n : n ≥ 0}, the standard non-regular context-free pattern.
Context-sensitive boundary
Consider the standard grammar:
S→aSBC | aBC
CB→BC
aB→ab
bB→bb
bC→bc
cC→ccThe production CB→BC has two symbols on its left-hand side, so this grammar is not context-free. Every production is length-preserving or length-increasing, and every left-hand side contains a non-terminal. It therefore fits Type 1. The construction generates {a^n b^n c^n : n ≥ 1}.
Unrestricted boundary
Now add one contracting rule to the same grammar: ABC→ε, where A is a fresh non-terminal alongside B and C.
Its left side has length 3, while its right side has length 0. That one contraction breaks the monotonic condition, so the written grammar no longer fits Type 1. The left side contains non-terminals, which is sufficient for an unrestricted rule. The grammar is Type 0.
That gives a useful boundary ladder: one consistently linear non-terminal, then a single-non-terminal left side, then a non-contracting multi-symbol left side, then a contracting rule.
4. The traps that flip a classification
Mixed orientation: a grammar containing right-linear and left-linear forms fails the standard single-orientation Type 3 test. It remains context-free if every left side is one non-terminal.
A non-terminal between terminals:
A→aBcis a valid context-free rule, but it is not regular.One contracting production: if
|LHS| > |RHS|, the usual Type 1 monotonic test fails for the entire grammar.The epsilon exception:
S→εmay be admitted in a context-sensitive grammar when the language contains the empty string andSdoes not appear on any right-hand side. Check the convention stated in the question.Grammar versus language: an unrestricted grammar can happen to generate a regular language. If the question asks for the grammar's class, inspect its productions. If it asks for the language's tightest class, reason about the language.
The last distinction is the subtle one. Production shape settles grammar classification. Language classification may require closure properties, a pumping argument, or a machine construction.
5. How the exam tests this
Common versions ask for the grammar type, the tightest class containing a language, or a match between productions and Chomsky classes. Another version gives two languages and asks which is regular, context-free or context-sensitive. Classify each one independently before comparing the options. The recurring trap sets the grammar against the language it generates: G = {S→SS, S→a} is Type 2, because SS is not a linear right-hand side, yet the language it generates is {a^n : n ≥ 1}, which is regular. Read which of the two the question asked for before you choose between Type 2 and Type 3.
For the current syllabus wording and paper conventions, use the official GATE portal of the organising IIT. Classification also pays off in Compiler Design, where the regular versus context-free split is the line between the lexer and the parser, so revise the two subjects together. The GATE category collects both.
If the question combines grammars with machine acceptance, revise context-free grammars and pushdown automata. For targeted practice, the theory of computation CFG question set keeps the classification rules beside related derivation questions. Our Theory of Computation question bank runs to well over a thousand questions, so keep scanning productions until the check takes seconds rather than minutes.
6. The short version and your next step
Check the left-hand side first. If it is a single non-terminal, decide between regular and context-free by inspecting the right side. If it is not, test monotonicity to separate context-sensitive from Type 0. Then let the least restrictive production fix the grammar's final class.
Build the full machine-and-language picture with the Theory of Computation course, then place it inside a complete preparation sequence with GATE Guidance by Sanchit Sir. Rewrite the four boundary grammars from memory and classify each rule aloud.
