Match List I with List II
| List I | List II |
|---|---|
| A. Type-0 Grammar | I. Linear Grammar |
| B. Type-1 Grammar | II. GNF |
| C. Type-2 Grammar | III. x → y, |x| ≤ |y|; x, y ∈ (V ∪ T)* |
| D. Type-3 Grammar | IV. Recursively Enumerable |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. A-IV, B-III, C-I, D-II
Explanation
Type 0 grammars generate recursively enumerable languages (A-IV), and Type 1 (context-sensitive) grammars have rules x → y with |x| ≤ |y| (B-III). Only option D has both pairs. (It pairs Type 2 with 'linear grammar' and Type 3 with GNF.)More Theory of Computation and Compilers questions
- Which of the following CFG(s) is/are in Chomsky Normal Form? (All capital letters are variables & lower case letters are terminals) A. S →…
- yacc is which of the following parsers?
- For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).
- For the above specified passage, which of the following represents the grammar for the language accepted by the machine?
- Which of the following represents the minimum-state DFA for the above specified passage?
- For the above specified passage, which of the following is a DFA for the language accepted by the machine?