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

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?
Find the option which resembles the given PDA
a) {0n1n|n>=0}
b) {0n12n|n>=0}
c) {02n1n|n>=0}
d) None of the mentioned
View Answer

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

4. Which of the following correctly resembles the given state diagram?
The given state diagram resembles {wwr|w=(a+b)*}
a) {wwr|w=(a+b)*}
b) ε is called the initial stack symbol
c) All of the mentioned
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.
advertisement

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

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

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.

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.