Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 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

Previous Post Next Post

Responsive Ad