Choose the correct answer from the options given below:
2025
Choose the correct answer from the options given below:
- A.
A → II, B → III, C → IV, D → I
- B.
A → III, B → I, C → IV, D → II
- C.
A → IV, B → I, C → II, D → III
- D.
A → III, B → II, C → I, D → IV
Attempted by 98 students.
Show answer & explanation
Correct answer: C
Concept: The Chomsky hierarchy classifies a grammar by the shape it allows on the two sides of a production α → β. A regular (Type-3) grammar restricts every production to a linear form; a context-free (Type-2) grammar allows only a single non-terminal on the left with any string on the right; a context-sensitive (Type-1) grammar rewrites a non-terminal only inside a fixed surrounding context, with the replacement conventionally not shortening the sentential form; an unrestricted (Type-0) grammar drops every restriction on both sides.
Grammar Type | Defining Restriction | Matching Form |
|---|---|---|
A. Type-3 (Regular) | linear production: one variable expands to a variable followed by a terminal, or a terminal alone | IV. V → VΣ | Σ |
B. Type-2 (Context-Free) | single non-terminal on the left, any string over (V∪Σ) on the right | I. V → (V∪Σ)* |
C. Type-1 (Context-Sensitive) | a variable is rewritten only within a fixed context λ, β; by convention the replacement does not shorten the string | II. λVβ → λ(V∪Σ)*β |
D. Type-0 (Unrestricted) | no restriction at all on either side | III. (V∪Σ)* → (V∪Σ)* |
Cross-check: The four grammar types are strictly nested, Type-3 ⊂ Type-2 ⊂ Type-1 ⊂ Type-0, from most to least restrictive, and the four production forms follow exactly that same order of restrictiveness — IV (linear) is the tightest, then I (single-variable left side), then II (context-preserving, conventionally non-shortening), then III (no restriction at all) — which independently confirms the pairing above.
So the complete match is A → IV, B → I, C → II, D → III.