Match the LIST-I with LIST-II Choose the correct answer from the options given below: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
A-IV, B-III, C-II, D-I
The Chomsky hierarchy classifies grammars by the form of their productions: Type 0 (unrestricted) grammars generate the recursively enumerable languages, Type 1 (context-sensitive) grammars have non-contracting productions x→y with |x| ≤ |y|, Type 2 (context-free) grammars have a single non-terminal on the left and can be put into normal forms such as Greibach Normal Form, and Type 3 (regular) grammars are the right- or left-linear grammars.
Step 1 — A (Type 0): unrestricted grammars generate exactly the recursively enumerable languages, so A-IV.
Step 2 — B (Type 1): the production form x→y with the left side never longer than the right side (non-contracting) defines context-sensitive grammars, so B-III.
Step 3 — C (Type 2): Greibach Normal Form (every production A→aα) is a normal form of context-free grammars, so C-II.
Step 4 — D (Type 3): regular grammars are linear grammars of the restricted right-linear or left-linear kind, so D-I.
The complete matching is therefore A-IV, B-III, C-II, D-I. The codes A-I, B-II, C-III, D-IV and A-II, B-I, C-III, D-IV pair Type 0 with linear grammar or GNF, which are far too weak for unrestricted grammars, and A-III, B-II, C-IV, D-I pairs Type 1 with GNF and Type 2 with recursively enumerable languages.
A-IV, B-III, C-II, D-I option is correct.
Similar Questions
Match the following :
List – I List – II a. Context free grammar i. Linear bounded automaton b. Regular grammar ii. Pushdown automaton c. Context sensitive grammar iii. Turing machine d. Unrestricted grammar iv. Deterministic finite automaton Codes :
a b c d
Given the recursively enumerable language (\(L_{RE}\)), the context sensitive language (\(L_{CS}\)), the recursive language (\(L_{REC}\)), the context free language (\(L_{CF}\)) and deterministic context free language (\(L_{DCF}\)). The relationship between these families is given by
The family of context sensitive languages is __________ under union and __________ under reversal.
Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy :
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted Grammars
Choose the correct answer from the options given below :
Which of the following is ε-free grammar?
Which of the following pairs have different expressive power ?
Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct ?
Important Questions from Automata Theory Concepts - Teaching
- Which of the following is FALSE ?
- Match List I with List II
List I List II A. Type 3 Grammar I. V $\rightarrow$ (V $\cup$$\Sigma$)* B. Type 2 Grammar II. $\lambda$V$\beta$ $\rightarrow$ $\lambda$(V $\cup$$\Sigma$)*$\beta$, where ($\lambda$,$\beta$)$\epsilon$(V $\cup$$\Sigma$)* C. Type 1 Grammar III. (V $\cup$$\Sigma$)* $\rightarrow$ (V $\cup$$\Sigma$)* D. Type 0 Grammar IV. V $\rightarrow$ V$\Sigma$|$\Sigma$
Choose the correct answer from the options given below: Match the following :
List – I List – II a. Context free grammar i. Linear bounded automaton b. Regular grammar ii. Pushdown automaton c. Context sensitive grammar iii. Turing machine d. Unrestricted grammar iv. Deterministic finite automaton Codes :
a b c d
Given the recursively enumerable language (\(L_{RE}\)), the context sensitive language (\(L_{CS}\)), the recursive language (\(L_{REC}\)), the context free language (\(L_{CF}\)) and deterministic context free language (\(L_{DCF}\)). The relationship between these families is given by
The family of context sensitive languages is __________ under union and __________ under reversal.
