Match List I with List II. List I: A. Type-0 grammar, B. Type-1 grammar, C. Type-2 grammar, D. Type-3 grammar. List II: I. Linear grammar; II. GNF; III. x → y, |x| ≤ |y|, x, y ∈ (V ∪ T)*; 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 generates recursively enumerable languages; Type 1 (context-sensitive) has non-contracting rules |x| ≤ |y|; Type 2 (context-free) can be put in Greibach Normal Form; Type 3 grammars are (right/left) linear.
More Theory of Computation and Compilers questions
- For the above mentioned passage which of the following is correct?
- Which of the following represented the minimum state DFA for the above specified passage?
- For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?
- For the above specified passage, which of the following represents the regular expression?
- Consider the Grammar: T → Qx Q → RS R → y ∣ ϵ S → z ∣ ϵ Here x, y, z are terminals and T, Q, R, S are non- terminals. What will be the foll…
- Which of the following tasks could be attained using syntax trees in compiler design ? (A) Type Checking (B) Code Generation (C) Code Optim…