Chapter:

30+ Unit 1 Solved MCQs

in Theory of Computation

Chapters

1.	= ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?
A.	L1 is regular but not L2
B.	L2 is regular but not L1
C.	Both L1 and L2 are regular
D.	Neither L1 nor L2 are regular
Answer» B. L2 is regular but not L1

discuss

2.	A spanning tree for a simple graph of order 24 has
A.	12 edges
B.	6 edges
C.	23 edges
D.	None of above.
Answer» C. 23 edges

discuss

3.	If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A.	3
B.	4
C.	6
D.	5
Answer» C. 6

discuss

4.	If G is a connected planar graph of v vertices e edges and r regions then
A.	v-e+r=2
B.	e-v+r=2
C.	v+e-r=2
D.	None of above.
Answer» A. v-e+r=2

discuss

5.	A Hamiltonian cycle in a Hamiltonian graph of order 24 has
A.	12 edges.
B.	24 edges
C.	23 edges
D.	None of above.
Answer» B. 24 edges

discuss

6.	If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A.	3
B.	4
C.	6
D.	5
Answer» C. 6

discuss

7.	The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c is
A.	is type 3
B.	is type 2 but not type 3
C.	is type 1 but not type 2
D.	is type 0 but not type 1
Answer» B. is type 2 but not type 3

discuss

8.	The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → bc is
A.	is type 3
B.	is type 2 but not type 3
C.	is type 1 but not type 2
D.	is type 0 but not type 1
Answer» C. is type 1 but not type 2

discuss

9.	The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a is
A.	is type 3
B.	is type 2 but not type 3
C.	is type 1 but not type 2
D.	is type 0 but not type 1
Answer» A. is type 3

discuss

10.	P, Q, R are three languages. If P & R are regular and if PQ=R, then
A.	Q has to be regular
B.	Q cannot be regular
C.	Q need not be regular
D.	Q has to be a CFL
Answer» C. Q need not be regular

discuss

11.	Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.
A.	1 only
B.	2 only
C.	Both 1 and 2 are true statements
D.	None is true
Answer» C. Both 1 and 2 are true statements

discuss

12.	Automaton accepting the regular expression of any number of a ' s is:
A.	a*
B.	ab*
C.	(a/b)*
D.	abc
Answer» A. a*

discuss

13.	Grammars that can be translated to DFAs:
A.	Left linear grammar
B.	Right linear grammar
C.	Generic grammar
D.	All of these
Answer» B. Right linear grammar

discuss

14.	Two strings x and y are indistinguishable if:
A.	δ(s, x) = δ (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
B.	if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A
C.	Both above statements are true
D.	None of the above
Answer» C. Both above statements are true

discuss

15.	Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:
A.	N2
B.	2N
C.	2N
D.	N!
Answer» C. 2N

discuss

16.	Regular expressions are
A.	Type 0 language
B.	Type 1 language
C.	Type 2 language
D.	Type 3 language
Answer» A. Type 0 language

discuss

17.	The regular expression 0(10) denotes the same set as
A.	(10)1*
B.	0+(0+10)*
C.	(0+1)10(0+1)
D.	None of the above
Answer» B. 0+(0+10)*

discuss

18.	Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
A.	L1 = {0,1}* − L
B.	L1 = {0,1}*
C.	L1 is a subset of L
D.	L1 = L
Answer» A. L1 = {0,1}* − L

discuss

19.	Which of the statements is true:
A.	The complement of a regular language is always regular.
B.	Homomorphism of a regular language is always regular.
C.	Both of the above are true statements
D.	None of the above
Answer» C. Both of the above are true statements

discuss

20.	The regular sets are closed under:
A.	Union
B.	Concatenation
C.	Kleene closure
D.	All of the above
Answer» D. All of the above

discuss

21.	Any given transition graph has an equivalent:
A.	regular
B.	DFSM (Deterministic Finite State Machine)
C.	NDFSM
D.	All of them
Answer» D. All of them

discuss

22.	A language is regular if and only if
A.	Accepted by DFA
B.	Accepted by PDA
C.	Accepted by LBA
D.	Accepted by Turing machine
Answer» A. Accepted by DFA

discuss

23.	Which of the following is not a regular expression?
A.	[(a+b)-(aa+bb)]
B.	[(0+1)-(0b+a1)(a+b)]
C.	(01+11+10)*
D.	(1+2+0)(1+2)
Answer» B. [(0+1)-(0b+a1)(a+b)]

discuss

24.	Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is
A.	3
B.	5
C.	8
D.	9
Answer» D. 9

discuss

25.	How many strings of length less than 4 contains the language described by the regular expression (x+y)y(a+ab)?
A.	7
B.	10
C.	12
D.	11
Answer» D. 11

discuss

26.	Which of the following is TRUE?
A.	Every subset of a regular set is regular
B.	Every finite subset of a non-regular set is regular
C.	The union of two non-regular sets is not regular
D.	Infinite union of finite sets is regular
Answer» B. Every finite subset of a non-regular set is regular

discuss

27.	The minimum state automaton equivalent to the above FSA has the following number of states
A.	1
B.	2
C.	3
D.	4
Answer» B. 2

discuss

28.	Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)0(0+1)0(0+1)*?
A.	The set of all strings containing the substring 00.
B.	The set of all strings containing at most two 0’s.
C.	The set of all strings containing at least two 0’s.
D.	The set of all strings that begin and end with either 0 or 1.
Answer» C. The set of all strings containing at least two 0’s.

discuss

29.	Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
A.	n-1
B.	n
C.	n+1
D.	2n-1
Answer» C. n+1

discuss

30.	Which of the following are regular sets?
A.	I and IV only
B.	I and III only
C.	I only
D.	IV only
Answer» A. I and IV only

discuss

31.	A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
A.	15 states
B.	11 states
C.	10 states
D.	9 states
Answer» A. 15 states

discuss

32.	Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?
A.	P ∩ Q
B.	P – Q
C.	∑* – P
D.	∑* – Q
Answer» C. ∑* – P

discuss

33.	Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
A.	5
B.	4
C.	3
D.	2
Answer» C. 3

discuss

34.	Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?
A.	L must be either {an I n is odd} or {an I n is even}
B.	L must be {an I n is odd}
C.	L must be {an I n is even}
D.	L must be {an I n = 0}
Answer» A. L must be either {an I n is odd} or {an I n is even}

discuss

35.	The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .
A.	CFL
B.	CFG
C.	GTG
D.	None of the given
Answer» B. CFG

discuss

30+ Unit 1 Solved MCQs

= ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?

A spanning tree for a simple graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

If G is a connected planar graph of v vertices e edges and r regions then

A Hamiltonian cycle in a Hamiltonian graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c is

The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → bc is

The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a is

P, Q, R are three languages. If P & R are regular and if PQ=R, then

Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.

Automaton accepting the regular expression of any number of a ' s is:

Grammars that can be translated to DFAs:

Two strings x and y are indistinguishable if:

Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:

Regular expressions are

The regular expression 0*(10)* denotes the same set as

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

Which of the statements is true:

The regular sets are closed under:

Any given transition graph has an equivalent:

A language is regular if and only if

Which of the following is not a regular expression?

Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is

How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

Which of the following is TRUE?

The minimum state automaton equivalent to the above FSA has the following number of states

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Which of the following are regular sets?

A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has

Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?

Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is

Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?

The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .

The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S → aSa
S → aAa
A → bB
B → bB
B → c is

The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S → aAB
AB → CD
CD → CE
C → aC
C → b
bE → bc is

The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S → aS
A → bB
B → cC
C → a is

Which of the following is true with respect to Kleene’s theorem?
1 A regular language is accepted by a finite automaton.
2 Every language is accepted by a finite automaton or a turingmachine.

The regular expression 0(10) denotes the same set as

How many strings of length less than 4 contains the language described by the regular expression (x+y)y(a+ab)?

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)0(0+1)0(0+1)*?

Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?

Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below:
A B
P - Q
q R S
r R S
s R S
The minimum number of states required in Deterministic Finite Automation
(DFA) equivalent to NFA is