Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 1. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?

a. 226

b. 224

c. 225

d. 223


Ans- a. 226


2. Predict the analogous operation for the given language: A: {[p, q] | p ? A1, q does not belong to A2}

a. A1-A2

b. A2-A1

c. A1.A2

d. A1+A2


Ans- a. A1-A2


3. If L1 and L2 are regular languages, which among the following is an exception?

a. L1 U L2

b. L1 - L2

c. L1 ? L2

d. All of the mentioned


Ans- d. All of the mentioned


4. Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.

a. 16

b. 11

c. 5

d. 6


Ans- a. 16


5. A binary string is divisible by 4 if and only if it ends with:

a. 100

b. 1000

c. 1100

d. 11


Ans- a. 100


6. Given Language: {x | it is divisible by 3}; The total number of final states to be assumed in order to pass the number constituting {0, 1} is

a. 0

b. 1

c. 2

d. 3


Ans- c. 2


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


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


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

a. Lexical Analyzer

b. BOT

c. State charts

d. None of the mentioned


Ans- d. None of the mentioned


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

Previous Post Next Post

Responsive Ad