Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 1. Which among the following is not a part of the Context free grammar tuple?

a. End symbol

b. Start symbol

c. Variable

d. Production


Ans- a. End symbol


2. The following move of a PDA is on the basis of:

a. Present state

b. Input Symbol

c. Both (a) and (b)

d. None of the mentioned


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


3. A string is accepted by a PDA when

a. Stack is empty

b. Acceptance state

c. Both (a) and (b)

d. None of the mentioned


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


4. Which of the operations are eligible in PDA?

a. Push

b. Delete

c. Pop

d. Both (A) and (C)


Ans- d. Both (A) and (C)


5. A push down automaton with only symbol allowed on the stack along with fixed symbol.

a. Embedded PDA

b. Nested Stack automata

c. DPDA

d. Counter Automaton


Ans- d. Counter Automaton


6. The class of languages not accepted by non deterministic, nonerasing stack automata is ___

a. NSPACE(n2)

b. NL

c. CSL

d. All of the mentioned


Ans- d. All of the mentioned


7. Push down automata accepts ___ languages.

a. Type 3

b. Type 2

c. Type 1

d. Type 0


Ans- b. Type 2


8. A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.

a. 5

b. 8

c. 4

d. 10


Ans- d. 10


9. Which of the following allows stacked values to be sub-stacks rather than just finite symbols?

a. Push Down Automaton

b. Turing Machine

c. Nested Stack Automaton

d. None of the mentioned


Ans- c. Nested Stack Automaton


10. A push down automaton employs ____ data structure.

a. Queue

b. Linked List

c. Hash Table

d. Stack


Ans- d. Stack

Previous Post Next Post

Responsive Ad