The language L = {aⁿbⁿ | n ≥ 1} is context-free but not regular. What does this mean about its computational recognition?
AL can only be recognized by a linear-bounded automaton — a pushdown automaton is insufficient
BL can be recognized by a pushdown automaton but not by a finite automaton
CL can be recognized by a sufficiently large finite automaton, since n has a maximum in practice
DL is context-free, meaning it cannot be recognized by a Turing machine
Context-free means exactly: recognizable by a pushdown automaton (which has a stack) but not by a finite automaton (which has only fixed memory). Since the Chomsky hierarchy is a proper containment chain (Regular ⊂ CFL ⊂ CSL ⊂ RE), a CFL is also recognized by linear-bounded automata and Turing machines — higher levels include lower ones. A finite automaton cannot recognize L because it cannot count an unbounded number of a's to match against b's. Option D reverses the hierarchy: higher levels have more recognition power, not less.
Question 2 Multiple Choice
A programming language designer wants the syntax parseable by a deterministic pushdown automaton. Which grammar type should they target?
AType 0 (recursively enumerable), because unrestricted grammars are the most expressive
BType 3 (regular), because finite automata are the fastest parsers
CType 2 (context-free), because pushdown automata correspond to context-free grammars
DType 1 (context-sensitive), because real programming languages need context about surrounding symbols
Each level in the Chomsky hierarchy has a corresponding automaton class: Type 3 ↔ finite automata, Type 2 ↔ pushdown automata, Type 1 ↔ linear-bounded automata, Type 0 ↔ Turing machines. A deterministic pushdown automaton (DPDA) corresponds to a subset of context-free grammars — exactly what efficient parsers (LL, LR) use. Type 3 cannot express recursive structures like nested parentheses. Type 4 and Type 0 would be parseable in principle but not efficiently, and their grammar restrictions don't match what a DPDA requires.
Question 3 True / False
Every regular language is also a context-free language, because the Chomsky hierarchy is a proper containment chain (Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0).
TTrue
FFalse
Answer: True
The hierarchy is inclusive: a language at level k is a valid member of all higher levels. Any regular grammar can be simulated by a context-free grammar (add trivial productions), any CFL is context-sensitive, and so on. A language doesn't 'lose' its lower-level classification when we recognize it also belongs to a higher level. The containments are proper (each level strictly contains the previous), meaning each level is more expressive, not exclusive. Saying a language is regular tells you the minimum class needed — not the only class that can express it.
Question 4 True / False
A context-sensitive language cannot be recognized by a Turing machine — it requires exactly a linear-bounded automaton, no more.
TTrue
FFalse
Answer: False
The Chomsky hierarchy specifies the minimum computational resource needed for each language class. A Type 1 language requires at minimum a linear-bounded automaton (LBA), but a full Turing machine certainly can recognize it too — Turing machines are strictly more powerful than LBAs. 'Requires exactly an LBA' confuses the minimum bound with an exact bound. Every context-sensitive language is also recursively enumerable (Type 0), so Turing machines are always sufficient. The hierarchy tells you when you can get by with less, not that you must use exactly the minimum.
Question 5 Short Answer
Why does the Chomsky hierarchy pair each grammar type with an automaton class? What does this dual perspective reveal about language complexity?
Think about your answer, then reveal below.
Model answer: The pairing reveals that the structural complexity of grammar rules and the computational memory needed for recognition are two sides of the same phenomenon. Each grammar type's production restrictions correspond precisely to what a particular automaton can track: finite automata match right-linear grammars (no memory beyond current state), pushdown automata match context-free grammars (stack memory for recursive nesting), and so on.
The duality gives two complementary tools. To show a language IS at a given level, construct either the grammar or the automaton. To show it ISN'T, use a pumping lemma or undecidability argument. The hierarchy thus organizes both languages and the techniques for reasoning about them. Understanding where a language sits immediately tells you what parser to build and what proofs are available — it is a practical guide for compiler design and theoretical computer science alike.