From PDA to Grammars Multiple Choice Questions with Answers

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
View Answer

Answer: d
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
View Answer

Answer: a
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) {0ⁿ1ⁿ|n>=0}
b) {0ⁿ1²ⁿ|n>=0}
c) {0²ⁿ1ⁿ|n>=0}
d) None of the mentioned
View Answer

Answer: a

4. Which of the following correctly resembles the given state diagram?

a) {ww^r|w=(a+b)*}
b) ε is called the initial stack symbol
c) Both (a) and (b)
d) None of the mentioned
View Answer

Answer: a
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
View Answer

Answer: d
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
View Answer

Answer: d
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
View Answer

Answer: a
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
View Answer

Answer: c
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
View Answer

Answer: d
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
View Answer

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