# Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

1. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

a. L1<L2

b. L1>=L2

c. L1 U L2 = .*

d. L1=L2

**Ans- d. L1=L2**

2. Regular grammar is:

a. context free grammar

b. non context free grammar

c. english grammar

d. none of the mentioned

**Ans- a. context free grammar**

3. 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

**Ans- a. accepted by DFA**

4. Which of the following is true?

a. (01)0 = 0(10)

b. (0+1)0(0+1)*1(0+1) = (0+1)*01(0+1)

c. (0+1)01(0+1)+1*0* = (0+1)*

d. All of the mentioned

**Ans- d. All of the mentioned**

5. 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

**Ans- d. 11**

6. Which of the following pair of regular expression are not equivalent?

a. 1(01)* and (10)*1

b. x(xx)* and (xx)*x

c. (ab)* and a*b*

d. x+ and x*x+

**Ans- c. (ab)* and a*b***

7. (a+b)* is equivalent to

a. b*a*

b. (a*b*)*

c. a*b*

d. None of the mentioned

**Ans- b. (a*b*)***

8. Precedence of regular expression in decreasing order is :

a. * , . , +

b. . , * , +

c. . , + , *

d. + , a , *

**Ans- a. * , . , +**

9. Regular expression {0,1} is equivalent to

a. 0 U 1

b. 0 / 1

c. 0 + 1

d. All of the mentioned

**Ans- d. All of the mentioned**

10. A regular language over an alphabet a is one that can be obtained from

a. union

b. concatenation

c. kleene

d. All of the mentioned

**Ans- d. All of the mentioned**