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

1. The total number of states to build the given language using DFA: L= {w | w has exactly 2 a's and at least 2 b's}

a. 10

b. 11

c. 12

d. 13

**Ans- a. 10**

2. Predict the number of transitions required to automate the following language using only 3 states: L= {w | w ends with 00}

a. 3

b. 2

c. 4

d. Cannot be said

**Ans- a. 3**

3. L1= {w | w does not contain the string tr } L2= {w | w does contain the string tr}; Given ?= {t, r}, The difference of the minimum number of states required to form L1 and L2?

a. 0

b. 1

c. 2

d. Cannot be said

**Ans- a. 0**

4. Which among the following is not an application of FSM?

a. Lexical Analyser

b. BOT

c. State charts

d. None of the mentioned

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

5. Which among the following can be an example of application of finite state machine(FSM)?

a. Communication Link

b. Adder

c. Stack

d. None of the mentioned

**Ans- a. Communication Link**

6. Which of the following do we use to form an NFA from a regular expression?

a. Subset Construction Method

b. Power Set Construction Method

c. Thompson Construction Method

d. Scott Construction Method

**Ans- c. Thompson Construction Method**

7. John is asked to make an automaton which accepts a given string for all the occurrence of '1001' in it. How many number of transitions would John use such that, the string processing application works?

a. 9

b. 11

c. 12

d. 15

**Ans- a. 9**

8. Which of the following is an application of Finite Automaton?

a. Compiler Design

b. Grammar Parsers

c. Text Search

d. All of the mentioned

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

9. It is less complex to prove the closure properties over regular languages using:

a. NFA

b. DFA

c. PDA

d. Can't be said

**Ans- a. NFA**

10. Under which of the following operation, NFA is not closed?

a. Negation

b. Kleene

c. Concatenation

d. None of the mentioned

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