Which of the following pairs have different expressive power ?
Deterministic push down automata and non-deterministic pushdown automata.
Two machine models have the same expressive power when they accept exactly the same class of languages.
Turing machines are robust: a single-tape machine can simulate a multi-tape machine and a multi-dimensional machine (only with a polynomial slow-down), so single-tape, multi-tape and multi-dimensional Turing machines all accept exactly the recursively enumerable languages. The two pairs built from Turing machine variants therefore have equal power.
Finite automata: the subset construction converts any NFA into an equivalent DFA, so both accept exactly the regular languages — again equal power.
Pushdown automata: nondeterministic PDA accept all context free languages, while deterministic PDA accept only the deterministic context free languages, a proper subclass. The language of even-length palindromes {wwR} is accepted by an NPDA but by no DPDA, because a deterministic machine cannot know where the middle of the input lies.
Deterministic push down automata and non-deterministic pushdown automata. 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:
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?
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.
