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

1. |-* is the ____ closure of |-

a. symmetric and reflexive

b. transitive and reflexive

c. symmetric and transitive

d. none of the mentioned

Ans- b. transitive and reflexive

2. A PDA machine configuration (p, w, y) can be correctly represented as:

a. (current state, unprocessed input, stack content)

b. (unprocessed input, stack content, current state)

c. (current state, stack content, unprocessed input)

d. None of the mentioned

Ans- a. (current state, unprocessed input, stack content)

3. The transition a Push down automaton makes is additionally dependent upon the:

a. stack

b. input tape

c. terminals

d. none of the mentioned

Ans- a. stack

4. A push down automata is said to be ___ if it has atmost one transition around all configurations.

a. Finite

b. Non regular

c. Non-deterministic

d. Deterministic

Ans- d. Deterministic

5. Which of the following are the actions that operates on stack top?

a. Pushing

b. Popping

c. Replacing

d. All of the mentioned

Ans- d. All of the mentioned

6. Which of the following statement is false?

a. For non deterministic PDA, equivalence is undecidable

b. For deterministic PDA, equivalence is decidable

c. For deterministic PDA, equivalence is undecidable.

d. None of the mentioned

Ans- c. For deterministic PDA, equivalence is undecidable.

7. A push down automata can represented using:

a. Transition graph

b. Transition table

c. ID

d. All of the mentioned

Ans- d. All of the mentioned

8. The moves in the PDA is technically termed as:

a. Turnstile

b. Shifter

c. Router

d. None of the mentioned

Ans- a. Turnstile

9. The instantaneous PDA is has the following elements:

a. State

b. Unconsumed input

c. Stack content

d. All of the mentioned

Ans- d. All of the mentioned

10. Which among the following is true for the given statement ? Statement :If there are strings R and T in a language L so that R is prefix of T and R is not equivalent to T.

a. No DPDA can accept L by empty stack

b. DPDA can accept L by an empty stack

c. L is regular

d. None of the mentioned

Ans- a. No DPDA can accept L by empty stack