Match List I with List II. List I: A. Type 3 Grammar, B. Type 2 Grammar, C. Type 1 Grammar, D. Type 0 Grammar. List II: I. V → (V ∪ Σ)*; II. λVβ → λ(V ∪ Σ)*β, where λ, β ∈ (V ∪ Σ)*; III. (V ∪ Σ)* → (V ∪ Σ)*; IV. V → VΣ | Σ

1. AA → II, B → III, C → IV, D → I
2. BA → III, B → I, C → IV, D → II
3. CA → IV, B → I, C → II, D → III
4. DA → III, B → II, C → I, D → IV

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A → IV, B → I, C → II, D → III

Explanation

Type 3 (regular) rules have one terminal with at most one non-terminal: V → VΣ | Σ. Type 2 (context-free): single variable on the left. Type 1 (context-sensitive): a variable rewritten in context λ_β. Type 0: any string on either side.