Match the following: Item Grammar Match Automaton (i) Regular Grammar (a)…

Concept

The Chomsky hierarchy classifies grammars by the shape of their productions, and every grammar class corresponds exactly to one machine model: the languages a grammar type can generate are precisely the languages the matching machine can recognise. The ladder is ordered by how much memory the machine is given — finite control alone, then one stack, then a tape bounded by the length of the input, then an unbounded tape.

Applying it to this item

1. Regular Grammar (i): in the right-linear form every production looks like A → aB or A → a, and the left-linear form mirrors it, so the derivation only ever has to remember which non-terminal it is currently at. Finite-state memory is enough, and that machine is the deterministic finite automaton — letter (c).

2. Context free Grammar (ii): productions carry a single non-terminal on the left, A → α, which lets the grammar generate nested, balanced structure such as matched brackets. Tracking nesting needs last-in-first-out memory, and that machine is the pushdown automaton with its stack — letter (a).

3. Unrestricted Grammar (iii): productions α → β are unrestricted apart from requiring a non-terminal somewhere on the left, so the grammar generates exactly the recursively enumerable languages. Recognising those needs an unbounded read-write tape, and that machine is the Turing machine — letter (d).

4. Context Sensitive Grammar (iv): productions obey |α| ≤ |β|, so no derivation step ever shortens the sentential form and the working space never grows past the length of the input. A Turing machine whose tape is capped by the input is the linear bounded automaton — letter (b).

Reading the automaton letters in the order (i), (ii), (iii), (iv) therefore gives (c), (a), (d), (b).

Cross-check

The two ladders must line up in strength. The machines get strictly more powerful as finite control ⊂ stack ⊂ input-bounded tape ⊂ unbounded tape, while the grammars get strictly less restricted as Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0. So the most powerful machine, the Turing machine, has to sit with the least restricted grammar, the unrestricted one, and the linear bounded automaton, whose tape is capped by the input length, has to sit with the non-contracting context-sensitive productions. Swapping those two would break the ordering.