# Theory of Computation Solved MCQs

Chapters

Chapter: Unit 1
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
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.
3.

A. 3
B. 4
C. 6
D. 5
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.
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.
6.

A. 3
B. 4
C. 6
D. 5
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
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
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
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
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
12.

A. a*
B. ab*
C. (a/b)*
D. a*b*c
13.

## Grammars that can be translated to DFAs:

A. Left linear grammar
B. Right linear grammar
C. Generic grammar
D. All of these
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
15.

A. N2
B. 2N
C. 2N
D. N!
16.

## Regular expressions are

A. Type 0 language
B. Type 1 language
C. Type 2 language
D. Type 3 language
17.

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

A. (1*0)*1*
B. 0+(0+10)*
C. (0+1)*10(0+1)*
D. None of the above
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
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
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
21.

## Any given transition graph has an equivalent:

A. regular
B. DFSM (Deterministic Finite State Machine)
C. NDFSM
D. All of them
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
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)*
24.

A. 3
B. 5
C. 8
D. 9
25.

A. 7
B. 10
C. 12
D. 11