**Theory of Computer Science MCQ Questions Answers**

Computer Science Theory is the bedrock of the digital world we live in today. It encompasses the fundamental principles, concepts, and theories that underlie the development, design, and analysis of computer systems and algorithms. To gauge your understanding of this intricate field, Multiple Choice Questions (MCQs) provide an effective way to assess your knowledge. In this article, we’ll delve into various computer science theory MCQ questions and provide detailed answers to help you solidify your understanding.

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