**Theory of Computer Science MCQ Questions Answers**

1)How many states does the DFA construction for the set of all strings ending with ‘’00’’, have?

a)2

b) 3

c) 4

d) 5

2)How many minimum number of states will be there in the DFA accepting all strings (over the alphabet {a,b}) that do not contain two consecutive a’s

a) 2

b) 3

c) 4

d) 5

3) Strings generated by (1+01)* does not contain the substring,

a)10

b) 11

c) 01

d) none of the above

4) Con text free language are closed under

a) Union

b) Intersection

c)Complementation

d) Set Difference

5) A countable union of countable sets is not

a) Countable

b) Uncountable

c) Countable infinite

d) Denumerable

6)Which of the following regular expression des not represent strings beginning with at least one 0 and ends with at least one 1?

a) 0*1*

b) 00*(0+1)*1

c) 0(0+1)*1

d) None of the above

7) Any given transition diagram has an equivalent

a) regular expression

b) NDFSM

C) DFSM

d) all of these

8) Can a DFA simulate NFA?

a) no

b) Yes

c) some time

d) depends on NFA

9) The regular expression for ‘’Binary numbers that are multiples of two’’ is

a) (0/1)*1

b) (0/1)*0

c) (1/0)*1

d) (1/0)*00

10) Which of the following is in P?

PATH, HAMPATH, SAT, 3SAT

a)SAT

b)3SAT

c) PATH

d) HAMPATH