Chapter:

30+ Unit 3 Solved MCQs

in Theory of Computation

Chapters

60

16.6k

1

1.	Any Language generated by an unrestricted grammar is:
A.	Recursive
B.	Recursively Enumerable
C.	Not Recursive
D.	None of the above
Answer» A. Recursive

discuss

2.	The Family of recursive language is not closed under which of the following operations:
A.	Union
B.	Intersection
C.	Complementation
D.	None of the above.
Answer» D. None of the above.

discuss

3.	PCP is:
A.	Decidable
B.	Undecidable
C.	Sometimes Decidable
D.	None of the
Answer» B. Undecidable

discuss

4.	If PCP is decidable then MPCP is
A.	Decidable
B.	Undecidable
C.	Can’t Say
D.	None of the
Answer» C. Can’t Say

discuss

5.	Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is
A.	NP hard
B.	NP complete
C.	Recursive
D.	Recursively enumerable
Answer» D. Recursively enumerable

discuss

6.	Consider the following statements I. Recursive languages are closed under complementation II. Recursively enumerable languages are closed under union III. Recursively enumerable languages are closed under complementation Which of the above statement are TRUE?
A.	I only
B.	I and II
C.	I and III
D.	II and III
Answer» B. I and II

discuss

7.	Recursively enumerable languages are not closed under
A.	Union
B.	homomorphism
C.	complementation
D.	concatenation
Answer» C. complementation

discuss

8.	Which of the following problem is undecidable?
A.	Membership problem for CFL
B.	Membership problem for regular sets
C.	Membership problem for CSL
D.	Membership problem for type 0 languages
Answer» D. Membership problem for type 0 languages

discuss

9.	Recursive languages are
A.	A proper superset of CFL
B.	Always recognized by PDA
C.	Are also called type 0 languages
D.	Always recognized by FSA
Answer» A. A proper superset of CFL

discuss

10.	Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?
A.	X is decidable
B.	X is undecidable but partially decidable
C.	X is undecidable and not even partially decidable
D.	X is not a decision problem
Answer» A. X is decidable

discuss

11.	If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?
A.	yx
B.	xyx
C.	x
D.	xyxyx
Answer» D. xyxyx

discuss

12.	Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively
A.	Regular, regular
B.	Not regular, regular
C.	Regular, not regular
D.	Context free, not regular
Answer» D. Context free, not regular

discuss

13.	If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
A.	L1 L2
B.	L1 ∩ L2
C.	L1 ∩ R
D.	L1 ∪ L2
Answer» B. L1 ∩ L2

discuss

14.	The logic of pumping lemma is a good example of
A.	Pigeon-hole principle
B.	Divide-and-conquer technique
C.	Recursion
D.	Iteration
Answer» A. Pigeon-hole principle

discuss

15.	For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by
A.	(a + b ) * ab
B.	ab (a + b ) *
C.	a ( a + b ) * b
D.	b (a + b ) * a
Answer» D. b (a + b ) * a

discuss

16.	Pumping lemma is generally used for proving that
A.	Given grammar is regular
B.	Given grammar is not regular
C.	Whether two given regular expressions are equivalent or not
D.	None of these
Answer» B. Given grammar is not regular

discuss

17.	What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc
A.	Type 0
B.	Type 1
C.	Type 2
D.	Type 3
Answer» C. Type 2

discuss

18.	Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production A —>aB {print “(1)” A —> c {print “1”), B —>Ab {print *2”}. When parser is aaacbbb, then string printed
A.	0202021
B.	1202020
C.	1020202
D.	None of these
Answer» A. 0202021

discuss

19.	FSM can recognize
A.	Any grammar
B.	Only CG
C.	Both (a) and ( b )
D.	Only regular grammar
Answer» D. Only regular grammar

discuss

20.	Basic limitation of FSM is that it
A.	Cannot remember arbitrary large amount of information
B.	Sometimes fails to recognize grammars that are regular
C.	Sometimes recognizes grammars are not regular
D.	None of these
Answer» A. Cannot remember arbitrary large amount of information

discuss

21.	Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.
A.	1 and 2
B.	1 and 4
C.	2 and 3
D.	2 and 4
Answer» B. 1 and 4

discuss

22.	If L and L¯ are recursively enumerable, then L is
A.	Regular
B.	Context free
C.	Context sensitive
D.	Recursive
Answer» D. Recursive

discuss

23.	Which of the following problems is undecidable?
A.	Membership problem for CFGs
B.	Ambiguity problem for CFGs.
C.	Finiteness problem for FSAs.
D.	Equivalence problem for FSAs.
Answer» B. Ambiguity problem for CFGs.

discuss

24.	Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)
A.	Context Free Language
B.	Context sensitive language
C.	Regular language
D.	Languages recognizable by Turing machine
Answer» D. Languages recognizable by Turing machine

discuss

25.	Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognizable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation (4) Turing recognizable languages are closed under union and intersection.
A.	1 and 4 only
B.	1 and 3 only
C.	2 only
D.	3 only
Answer» C. 2 only

discuss

26.	Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is
A.	L = {s ε (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
B.	L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
C.	L = {s ε (0+1)* I no(s) is a 3 digit prime}
D.	L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4
Answer» D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4

discuss

27.	Which one of the following is true regarding FOTRAN?
A.	It is a context free language
B.	It is a context sensitive language
C.	It is a regular language
D.	None of the above
Answer» B. It is a context sensitive language

discuss

28.	Which statement is true?
A.	The PDA must have one accept state and one reject state
B.	The PDA must have one accept state and two reject state
C.	The PDA must have two accept state and two reject state
D.	There is no reject state in the PDA.
Answer» D. There is no reject state in the PDA.

discuss

29.	TM is more powerful than FSM because
A.	The tape movement is confined to one direction
B.	It has no finite state control
C.	It has the capability to remember arbitrary long sequences of input symbols
D.	None of these
Answer» B. It has no finite state control

discuss

30.	Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
A.	Both DHAM3 and SHAM3 are NP-hard
B.	SHAM3 is NP-hard, but DHAM3 is not
C.	DHAM3 is NP-hard, but SHAM3 is not
D.	Neither DHAM3 nor SHAM3 is NP-hard
Answer» A. Both DHAM3 and SHAM3 are NP-hard

discuss

31.	Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?
A.	1 only
B.	1 and 3
C.	2 and 3
D.	1,2 and 3
Answer» D. 1,2 and 3

discuss

32.	Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:
A.	3
B.	5
C.	8
D.	9
Answer» D. 9

discuss

33.	Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.
A.	{S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
B.	{S->aS,S->bA,A->bB,B->bBa,B->bB}
C.	{S->aaS,S->bbA,A->bB,B->ba}
D.	None of the above
Answer» A. {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}

discuss

34.	The production Grammar is {S->aSbb,S->abb} is
A.	type-3 grammar
B.	type-2 grammar
C.	type-1 grammar
D.	type-0 grammar
Answer» B. type-2 grammar

discuss

35.	Regular expression (x/y)(x/y) denotes the set
A.	{xy,xy}
B.	{xx,xy,yx,yy}
C.	{x,y}
D.	{x,y,xy}
Answer» B. {xx,xy,yx,yy}

discuss

36.	The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is :
A.	(0+1+2)*
B.	012*
C.	0* + 1 + 2
D.	(0+1)2
Answer» B. 012*

discuss

30+ Unit 3 Solved MCQs

Any Language generated by an unrestricted grammar is:

The Family of recursive language is not closed under which of the following operations:

PCP is:

If PCP is decidable then MPCP is

Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

Consider the following statements I. Recursive languages are closed under complementation II. Recursively enumerable languages are closed under union III. Recursively enumerable languages are closed under complementation Which of the above statement are TRUE?

Recursively enumerable languages are not closed under

Which of the following problem is undecidable?

Recursive languages are

Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?

Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively

If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

The logic of pumping lemma is a good example of

For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by

Pumping lemma is generally used for proving that

What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc

FSM can recognize

Basic limitation of FSM is that it

Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.

If L and L¯ are recursively enumerable, then L is

Which of the following problems is undecidable?

Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)

Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is

Which one of the following is true regarding FOTRAN?

Which statement is true?

TM is more powerful than FSM because

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?

Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:

Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.

The production Grammar is {S->aSbb,S->abb} is

Regular expression (x/y)(x/y) denotes the set

The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is :

Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?

Which of the following are decidable?
1) Whether the intersection of two regular language is infinite.
2) Whether a given context free language is regular.
3) Whether two push down automata accept the same language.
4) Whether a given grammar is context free.

Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?