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
\(L_{DCF} \subseteq L_{CF} \subseteq L_{CS} \subseteq L_{REC} \subseteq L_{RE}\)
The language families form a chain of inclusions (part of the Chomsky hierarchy). Each class is recognised by a more powerful machine than the one before it, so we place the smallest family first.
Every deterministic PDA is also a PDA, so \(L_{DCF} \subseteq L_{CF}\). The inclusion is proper: \(\{ww^R\}\) is context free but not deterministic context free.
Every context free language (without λ) can be generated by a context sensitive grammar and accepted by a linear bounded automaton, so \(L_{CF} \subseteq L_{CS}\).
Membership in a context sensitive language is decidable (an LBA has only finitely many configurations), so every such language is recursive: \(L_{CS} \subseteq L_{REC}\).
A recursive language is accepted by a Turing machine that always halts, which is in particular a Turing machine, so \(L_{REC} \subseteq L_{RE}\). The halting problem shows the reverse fails.
Chains that start with \(L_{CF} \subseteq L_{DCF}\) or end with \(L_{RE} \subseteq L_{REC}\) reverse a true inclusion, so the only valid chain is \(L_{DCF} \subseteq L_{CF} \subseteq L_{CS} \subseteq L_{REC} \subseteq L_{RE}\).
Hence, the answer is \(L_{DCF} \subseteq L_{CF} \subseteq L_{CS} \subseteq L_{REC} \subseteq L_{RE}\).
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
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:
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
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:
