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

1. The number of tuples in an extended Non Deterministic Finite Automaton:

a. 5

b. 6

c. 7

d. 4

Ans- a. 5

2. Which of the following option is correct?

a. NFA is slower to process and its representation uses more memory than DFA

b. DFA is faster to process and its representation uses less memory than NFA

c. NFA is slower to process and its representation uses less memory than DFA

d. DFA is slower to process and its representation uses less memory than NFA

Ans- c. NFA is slower to process and its representation uses less memory than DFA

3. NFA, in its name has 'non-deterministic' because of :

a. The result is undetermined

b. The choice of path is non-deterministic

c. The state to be transited next is non-deterministic

d. All of the mentioned

Ans- b. The choice of path is non-deterministic

4. An automaton that presents output based on previous state or current input:

a. Acceptor

b. Classifier

c. Transducer

d. None of the mentioned.

Ans- c. Transducer

5. FSM with output capability can be used to add two given integer in binary representation. This is:

a. TRUE

b. FALSE

c. May be true

d. None of the mentioned

Ans- a. TRUE

6. The basic limitation of finite automata is that:

a. It can't remember arbitrary large amount of information.

b. It sometimes recognize grammar that are not regular.

c. It sometimes fails to recognize regular grammar.

d. All of the mentioned

Ans- a. It can't remember arbitrary large amount of information.

7. How many DFA's exits with two states over input alphabet {0,1} ?

a. 16

b. 26

c. 32

d. 64

Ans- d. 64

8. Regular expression for all strings starts with ab and ends with bba is.

a. aba*b*bba

b. ab(ab)*bba

c. ab(a+b)*bba

d. All of the mentioned

Ans- c. ab(a+b)*bba

9. Finite automata requires minimum ___ number of stacks.

a. 1

b. 0

c. 2

d. None of the mentioned

Ans- b. 0

10. Language of finite automata is.

a. Type 0

b. Type 1

c. Type 2

d. Type 3

Ans- d. Type 3