Computer Science Theory MCQ Questions Answers CSE

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

View Answer
Option – b)

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

View Answer
Option – b)

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

a)10

b) 11

c) 01

d) none of the above

View Answer
Option – d)

4) Con text free language are closed under

a) Union

b) Intersection

c)Complementation

d) Set Difference

View Answer
Option – a)

5) A countable union of countable sets is not

a) Countable

b) Uncountable

c) Countable infinite

d) Denumerable

View Answer
Option – b)

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

View Answer
Option – a)

7) Any given transition diagram has an equivalent

a) regular expression

b) NDFSM

C) DFSM

d) all of these

View Answer
Option – d)

8) Can a DFA simulate NFA?

a) no

b) Yes

c) some time

d) depends on NFA

View Answer
Option – b)

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

View Answer
Option – b)

10) Which of the following is in P?

PATH,  HAMPATH, SAT, 3SAT

a)SAT

b)3SAT

c) PATH

d) HAMPATH

View Answer
Option – a)

error: Content is protected !!