Match List I with List II
| List I | List II |
|---|---|
| A. Type 3 Grammar | I. V → (V ∪ Σ)* |
| B. Type 2 Grammar | II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)* |
| C. Type 1 Grammar | III. (V ∪ Σ)* → (V ∪ Σ)* |
| D. Type 0 Grammar | IV. V → VΣ | Σ |
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): V → VΣ | Σ (A-IV). Type 2 (context-free): V → (V ∪ Σ)* (B-I). Type 1 (context-sensitive): αVβ → α(V ∪ Σ)⁺β (C-II). Type 0 (unrestricted): (V ∪ Σ)* → (V ∪ Σ)* (D-III).More Theory of Computation and Compilers questions
- Arrange the following parsers in increasing order of their power of handling grammars, i.e. from the least powerful parser to the most powe…
- What are the various LEADERS (leading statements) for the TAC given in the passage?
- Which of the following is the optimized version of the TAC given in the passage?
- Which of the following is the correct high level code for the TAC given in the passage?
- What blocks do Block 3 and Block 5 dominate in the flow graph for the TAC given in the passage? (Basic blocks: B1 = 100–102, B2 = 103, B3 =…
- Which of the following is the correct flow graph (adjacency matrix of basic blocks B1–B7, row → column means an edge) for the TAC given in…