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

1. Complement of (a + b)* will be

a. phi

b. null

c. a

d. b

Ans- a. phi

2. Which of the following is type 3 language ?

a. Strings of 0's whose length is perfect square

b. Palindromes string

c. Strings of 0's having length prime number

d. String of odd number of 0's

Ans- d. String of odd number of 0's

3. (a ^ 5b ^ 5)* is example of ____

a. Type 0 language

b. Type 1 language

c. Type 2 language

d. Type 3 language

Ans- d. Type 3 language

4. Homomorphism of a regular set is ___

a. Universal set

b. Null set

c. Regular set

d. Non regular set

Ans- c. Regular set

5. A _____ is a substitution such that h(a) contains a string for each a.

a. Closure

b. Interchange

c. Homomorphism

d. Inverse Homomorphism

Ans- c. Homomorphism

6. Reverse of (0+1)* will be:

a. Phi

b. Null

c. (0+1)*

d. (0+1)

Ans- c. (0+1)*

7. Reverse of a DFA can be formed by:

a. using PDA

b. making final state as non-final

c. making final as starting state and starting state as final state

d. None of the mentioned

Ans- c. making final as starting state and starting state as final state

8. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be:

a. Empty set

b. CFG

c. Decidable

d. Regular

Ans- d. Regular

9. If L1 and L2 are regular sets then intersection of these two will be:

a. Regular

b. Non Regular

c. Recursive

d. Non Recursive

Ans- a. Regular

10. Complement of regular sets are ___

a. Regular

b. CFG

c. CSG

d. RE

Ans- a. Regular