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 :
(C), (A), (B), (D)
The Chomsky hierarchy classifies grammars into four nested types; each type generates a proper superset of the languages generated by the type below it.
Step 1 — Type 3, Regular languages (C): finite automata; the least expressive.
Step 2 — Type 2, Context-free languages (A): pushdown automata; every regular language is context-free, but anbn is context-free and not regular.
Step 3 — Type 1, Context-sensitive languages (B): linear-bounded automata; anbncn is context-sensitive but not context-free.
Step 4 — Type 0, Unrestricted grammars (D): Turing machines; they generate all recursively enumerable languages, the most expressive class.
Placing context-free languages ahead of regular languages reverses Type 2 and Type 3, and placing unrestricted grammars before context-sensitive languages reverses Type 0 and Type 1, so only the regular, context-free, context-sensitive, unrestricted order is ascending.
(C), (A), (B), (D) 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.
Match the 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 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.
