How do you read a grammar's production rules to place it at Chomsky type 3, 2, 1 or 0?
answer
- Look at rule shape, not output
- Count symbols on the left side
- Right side: one terminal or many
- Type 1 rules never shorten
- Grammar's tier differs from language's tier
basics
~20 sEach Chomsky tier restricts rule shape. Type 3: one terminal plus at most one non-terminal on the right, every rule leaning the same way. Type 2: a single non-terminal on the left. Type 1: no rule shortens. Type 0: unrestricted.
solid answer
~50 sRead the shape of each rule, not the strings it produces. A **type 3** (regular) grammar allows only `A -> a B` and `A -> a` — one terminal plus at most one non-terminal — and every rule must lean the same way; mixing left-linear and right-linear rules forfeits the guarantee. **Type 2** (context-free) keeps exactly one non-terminal on the left and frees the right side entirely, which is what makes nesting expressible. **Type 1** (context-sensitive) lets the left side carry fixed context around a non-terminal, and the practical test is that no rule shortens: `|left| <= |right|`. **Type 0** drops every restriction. The grammar's tier is the loosest one any single rule forces. And a grammar's tier is not its language's tier — a language sits at the lowest tier for which *some* grammar exists, so a clumsy grammar can sit above the language it generates.
code
pseudocode · 20 linestier = 3 // smaller number = looser restriction
leaning = NONE
for each rule (lhs -> rhs) in grammar:
if lhs is not exactly one nonterminal:
if length(lhs) <= length(rhs):
tier = min(tier, 1) // never shortens -> type 1
else:
tier = min(tier, 0) // shortens -> type 0
else if rhs is "terminal nonterminal" or "terminal" or empty:
leaning = combine(leaning, RIGHT)
else if rhs is "nonterminal terminal":
leaning = combine(leaning, LEFT)
else:
tier = min(tier, 2) // one nonterminal on left -> type 2
if tier == 3 and leaning == BOTH:
tier = 2 // mixed leaning loses the type-3 guarantee
return tiergo deeper
Recall that the hierarchy has four numbered tiers, and that the number falls as the rules get looser: type 3 is the tightest shape and type 0 has no restriction at all beyond needing a non-terminal on the left.
Explain each restriction concretely: a single non-terminal on the left for type 2, one terminal plus at most one non-terminal on the right for type 3, and no rule that shortens its input for type 1. Show the test rule by rule.
Show that you separate a grammar's tier from its language's tier, and that you check every rule before claiming a tier — one non-conforming production demotes the whole grammar, and one untidy grammar says nothing about the language.
Frame the tier as a cost decision rather than a label. The restriction you accept on rule shape is exactly what buys the cheap recogniser, the bounded validation time and the ability to reject hostile input at a trust boundary.
## What a tier classifies The Chomsky hierarchy classifies **grammars** — finite rule systems — and only indirectly the languages they generate. A grammar is built over two disjoint alphabets: **terminals**, the symbols that survive into the finished string, and **non-terminals**, placeholders that must be rewritten. Its **productions** are written `left -> right`, and you derive a string by starting from the start symbol and repeatedly replacing an occurrence of some production's left side with that production's right side, until nothing but terminals remains. The tier is a **purely syntactic restriction on what a production may look like**. You can classify a grammar by reading its rules, without deriving a single string from it. That is the whole trick, and it is why the hierarchy earns its place in a design discussion rather than only in a lecture: you can look at a rule set on a whiteboard and say what class of machine will be needed to check input against it. ## The four rule shapes | Tier | Restriction on every production | Typical rule | Common name | |---|---|---|---| | 3 | one non-terminal on the left; right side is a single terminal, optionally with one non-terminal, all rules leaning the same way | `A -> a B`, `A -> a` | regular | | 2 | one non-terminal on the left; right side is any string at all | `A -> a B c A` | context-free | | 1 | left side may surround one non-terminal with fixed context; no rule is shorter on the right than on the left | `α A β -> α γ β` | context-sensitive | | 0 | left side need only contain at least one non-terminal | `A B -> C` | unrestricted | - **Type 3** is the tightest. The right side carries at most one non-terminal, so a derivation is a single unbranching chain that grows the string one symbol at a time. Every rule must be *right*-linear (`A -> a B`) or every rule must be *left*-linear (`A -> B a`); a grammar that mixes the two is no longer type 3, and mixed grammars can generate sets no finite-state machine accepts. - **Type 2** keeps the single non-terminal on the left — that is exactly what "context-free" means: the rule applies to `A` wherever `A` occurs, with no regard for its neighbours — while freeing the right side completely. Branching right-hand sides are what make recursive, nested structure expressible. - **Type 1** allows a rule to fire only in a stated context: `α A β -> α γ β` rewrites `A` into `γ` when it sits between `α` and `β`, and leaves `α` and `β` themselves untouched. The equivalent and far easier test is **non-contracting**: `|left| <= |right|` for every rule. - **Type 0** drops everything except the requirement that the left side contain a non-terminal. Rules may delete, shorten, and rewrite several symbols at once. ## The test, rule by rule 1. Look at the **left** side. Is it exactly one non-terminal? If not, this rule is type 1 or type 0. 2. If the left side is longer than one symbol, compare lengths. If every such rule satisfies `|left| <= |right|`, the grammar is type 1; if any rule shortens, it is type 0. 3. If the left side is one non-terminal, look at the **right** side. Is it a lone terminal, or a terminal with one non-terminal, consistently on the same side, in every rule? Then type 3; otherwise type 2. The grammar's tier is the loosest tier that any single rule forces. One production with two symbols on the left drops the whole grammar out of type 2, however tidy the other forty are. ## The empty-string technicality A non-contracting grammar cannot derive the empty string, because no step can ever shrink a sentential form. Context-sensitive languages that happen to contain the empty string are handled by a standard convention: the rule `S -> ε` is permitted for the start symbol alone, provided `S` never appears on any right-hand side. It is bookkeeping, not a hole in the restriction, and it is worth knowing because it is the one place the clean `|left| <= |right|` test has an exception. ## A grammar's tier is not its language's tier This distinction separates someone who has used the hierarchy from someone who has only read about it. - A **grammar's** tier is a fact about its rules, checkable mechanically in one pass. - A **language's** tier is the lowest tier for which *some* grammar generating it exists. - So a grammar can sit above the language it generates: nothing stops you writing an unrestricted grammar for a set of three fixed strings. - It follows that exhibiting one non-type-3 grammar proves nothing at all about the language. Showing that a language is *not* regular takes an argument about the language itself, not about one rule set that happens to be untidy. - The tiers are **nested**, not disjoint: every type 3 grammar is already a legal type 2 grammar, and so on upward. Note that the containment runs opposite to the numbering — regular sits inside context-free sits inside context-sensitive sits inside the unrestricted class. ## What the restriction buys Every restriction you accept on rule shape is repaid as a cheaper checker. The tighter the shape, the less memory the machine that recognises the language needs, and the more you can promise about how much time and space validation takes on input you did not write. That is the reason a working engineer cares which shape their rules have, rather than treating the tier as trivia.
- Can a grammar that looks unrestricted still generate a regular language?Yes. The tier is a property of the rules, not of the set of strings. Nothing stops you writing a needlessly permissive grammar for a trivially finite-state language. The language's tier is the lowest one for which *some* grammar exists, so proving a language is not regular needs an argument about the language, never about one grammar you happened to write.
- Why must a regular grammar keep every rule linear on the same side?Because mixing the two smuggles in memory. Right-linear rules build the string front to back, the way a finite-state run does. Left-linear rules build it the other way. Allow both in one grammar and you can pair a symbol added at the front with one added at the back — `S -> a A`, `A -> S b` derives strings with matched counts, which no finite-state machine accepts.
- What does the non-shortening test actually buy you at type 1?A bound. No step can ever produce a sentential form longer than the string being derived, so for a given input the set of forms worth exploring is finite. That is what pairs type 1 with a machine whose working space is limited to the input region, and it is why membership in a context-sensitive language is a terminating search rather than an open-ended one.
saying these in an interview costs you the question
- Decides the tier from the language, never from the rules
- Assumes any self-referential rule rules out type 3
- Mixes left- and right-linear rules and still claims regular
- Thinks a context-sensitive rule may rewrite its own context
- Treats the four tiers as disjoint rather than nested