# Automata Theory Questions and Answers – From PDA to Grammars

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “From PDA to Grammars”.

1. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned

Explanation: The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.

2. The moves in the PDA is technically termed as:
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned

Explanation: A turnstile notation is used for connecting pairs od ID’s taht represents one or many moves of a PDA.

3. Which of the following option resembles the given PDA? a) {0n1n|n>=0}
b) {0n12n|n>=0}
c) {02n1n|n>=0}
d) None of the mentioned

Explanation: None.
Note: Join free Sanfoundry classes at Telegram or Youtube

4. Which of the following correctly resembles the given state diagram? a) {wwr|w=(a+b)*}
b) ε is called the initial stack symbol
c) All of the mentioned
d) None of the mentioned

Explanation: Initially we put a special symbol ‘#’ into the empty stack. At state q1, the w is being read. In state q2, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA will go to a dead state. When we reach that special symbol ‘#’, we go to the accepting state q3.

5. Which of the following assertion is false?
a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty stack i.e. L=L(PDA1)=L(PDA2)
b) If L is a CFL then there exists a push down automata P accepting CF; by empty stack i.e. L=M(P)
c) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P)
d) All of the mentioned

Explanation: All the assertions mentioned are theorems or corollary.

6. A push down automata can represented using:
a) Transition graph
b) Transition table
c) ID
d) All of the mentioned

Explanation: Yes, a PDA can be represented using a transition diagram, transition table and an instantaneous description.

7. State true or false:
Statement: Every context free grammar can be transformed into an equvalent non deterministic push down automata.
a) true
b) false

Explanation: Push down automata is the automaton machine for all the context free grammar or Type 2 languages.

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

Explanation: Geraud proved the equivalence problem decidable for Deterministic PDA .

9. Which of the following are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
d) All of the mentioned

Explanation: Push, pop and replace are all the basic and only operations that takes place on stack top.

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

Explanation: DPDA or Deterministic Push down automata has atmost one transition applicable to each configuration.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers. 