Theory of Computation (3160704) MCQs

MCQs of Pushdown Automata, CFL And NCFL

Showing 21 to 20 out of 30 Questions
1 2 3
21.
Which of the following language cannot be accepted by PDA:
(a) L=anbn+mcm|n,m>=1
(b) L=anbmcmdn|n,m>=1
(c) L=anbncmdm| n,m>=1
(d) L=anbncn|n,m>=1
Answer:

Option (d)

22.
Limitation of PDA can overcome by:
(a) Mealy machine
(b) Moore machine
(c) Turing machine
(d) FA
Answer:

Option (c)

23.
Can we convert PDA to equivalent CFG?
(a) Yes
(b) No
(c) May be
(d) Can’t say
Answer:

Option (a)

24.
Which of the following pairs have different expressive power?
(a) DFA and NFA
(b) DPDA and NPDA
(c) Deterministic single tape Turing machine & Non deterministic single tape Turing machine
(d) Single tape Turing machine and multi tape Turing machine
Answer:

Option (b)

25.
If L1 and L2 are two context free languages, then which one is true?
(a) L1 ∪ L2 is context free
(b) L1.L2 is context free
(c) Kleene closure L1* is context free
(d) All of these
Answer:

Option (d)

26.
CFL are not closed under Intersection and Complementation
(a) True
(b) False
(c) May be
(d) Can't say
Answer:

Option (a)

27.
The language L={0i12i | i ≥ 0} over the alphabet {0, 1, 2} is :
(a) Not recursive
(b) Recursive and deterministic CFL
(c) Regular
(d) CFL but not deterministic CFL
Answer:

Option (b)

28.
Consider the following languages: L1={0n1n|n≥0}L2={wcwr|w ɛ a,b*}L3={wwr|w ɛ a,b*} Which of these languages are deterministic context-free languages?
(a) None of the languages
(b) Only L1
(c) Only L1 and L2
(d) All three languages
Answer:

Option (c)

29.
The pumping lemma is often used to prove that a language is:
(a) Context free
(b) Regular
(c) Not context free
(d) None of the mentioned
Answer:

Option (c)

30.
We cannot use Ogden’s lemma when pumping lemma fails.
(a) True
(b) False
(c) May be
(d) Can't say
Answer:

Option (b)

Showing 21 to 20 out of 30 Questions
1 2 3