Automata Theory Questions and Answers – Deterministic PDA

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Deterministic PDA”

1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
View Answer

Answer: a
Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.

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

Answer: a
Explanation: A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).

3. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
View Answer

Answer: b
Explanation: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)
advertisement
advertisement

4. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
View Answer

Answer: d
Explanation: The empty stack in the end is our requirement relative to finite state automatons.

5. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
View Answer

Answer: a
Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false
View Answer

Answer: a
Explanation: There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence

7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) all of the mentioned
d) none of the mentioned
View Answer

Answer: a
Explanation: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.
advertisement

8. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: a
Explanation: Deterministic Context free languages(one accepted by PDA by final state), are drastically different from the context free languages. For example they are closed under complementation and not union.

9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
View Answer

Answer: a
Explanation: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.
advertisement

10. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
View Answer

Answer: a
Explanation: The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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 & discussions at Telegram SanfoundryClasses.