Automata Theory Multiple Choice Questions 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
Answer: d
Clarification: 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
Answer: a
Clarification: 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 are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
d) All of the mentioned
Answer: d
Clarification: Push, pop and replace are all the basic and only operations that takes place on stack top.
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
Answer: d
Clarification: DPDA or Deterministic Push down automata has atmost one transition applicable to each configuration.
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
Answer: d
Clarification:
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
Answer: d
Clarification: 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
Answer: a
Clarification: 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
Answer: c
Clarification: Geraud proved the equivalence problem decidable for Deterministic PDA .