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

1. Pick the odd one out of the given properties of a regular language:

a. Kleene

b. Reversal

c. Homomorphism

d. Membership

Ans- d. Membership

2. Which of the following are decision properties?

a. Emptiness

b. Infiniteness

c. Membership

d. All of the mentioned

Ans- d. All of the mentioned

3. Language classes have the following property:

a. Closure property

b. Decision property

c. Closure & Decision property

d. None of the mentioned

Ans- c. Closure & Decision property

4. NFA to DFA conversion is done via:

a. Subset Construction method

b. Warshalls Algorithm

c. Ardens theorem

d. None of the mentioned

Ans- a. Subset Construction method

5. Which of the following cannot be converted in an ordinary NFA?

a. DFA

b. Regular Expression

c. e-NFA

d. None of the mentioned

Ans- d. None of the mentioned

6. The conversion of NFA to DFA can be done in:

a. exponential time

b. linear time

c. logarithmic time

d. all of the mentioned

Ans- a. exponential time

7. Conversion of regular expression to e-NFA takes _____ time.

a. linear

b. exponential

c. logarithmic

d. none of the mentioned

Ans- a. linear

8. With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can ___ the size of the regular expression constructed.

a. double

b. triple

d. none of the mentioned

9. The computation of e-closure of n-states takes __ time.

a. O(n^2)

b. O(n^3)

c. O(2^n)

d. None of the mentioned

Ans- b. O(n^3)

10. Which of the following conversion is not feasible?

a. Regular expression to automaton conversion

b. Automaton to Regular Expression Conversion

c. NFA to DFA

d. None of the mentioned

Ans- d. None of the mentioned

11. Which of the following is a function of Closure properties?

a. Helps construct representations

b. Helps show informally described languages not to be in class

c. Both (a) and (b)

d. None of the mentioned

Ans- c. Both (a) and (b)

12. Which of the following problems do not belong to decision properties?

a. Given two languages, are there strings that are in both

b. Is the language a subset of another regular language

c. Is the language same as another regular language

d. None of the mentioned

Ans- d. None of the mentioned

13. Which of the following are not meant to specify a regular language?

a. Regular Expression

b. DFA

c. NDFA and epsilon-NFA

d. All of the mentioned

Ans- d. All of the mentioned

14. For an automata, which of the following are equivalent variants? DFA,NFA and NFA with epsilon transitions

a. DFA and NFA

b. NFA and epsilon NFA

c. DFA and epsilon NFA

d. All of the mentioned

Ans- d. All of the mentioned