Automata Theory Questions and Answers – PDA-Acceptance by Final State


This set of Automata Theory Questions and Answers for Entrance exams focuses on “PDA-Acceptance by Final State”.

1. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
View Answer

Answer: d
Explanation: A push down automata uses a stack to carry out its operations. They are more capable than the finite automatons but less than the turing model.

2. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
View Answer

Answer: a
Explanation: The term pushdown refers to the fact that the elements are pushed down in the stack and as per the LIFO principle, the operation is always performed on the top element of the stack.

3. Which of the following allows stacked values to be sub-stacks rather than just finite symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
View Answer

Answer: c
Explanation: In computational theory, a nested stack automaton is a finite automaton which makes use of stack containing data which can be additional stacks.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

4. A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
a) 5
b) 8
c) 4
d) 10
View Answer

Answer: d
Explanation: The 10-tuple can be stated as: NSA= <Q,Σ,Γ,δ,q0,Z0,F,[,],]>.

5. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
View Answer

Answer: b
Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.

6. The class of languages not accepted by non deterministic, nonerasing stack automata is _______
a) NSPACE(n2)
b) NL
c) CSL
d) All of the mentioned
View Answer

Answer: d
Explanation: NSPACE or non deterministic space is the computational resource describing the memory space for a non deterministic turing machine.

7. A push down automaton with only symbol allowed on the stack along with fixed symbol.
a) Embedded PDA
b) Nested Stack automata
d) Counter Automaton
View Answer

Answer: d
Explanation: This class of automata can recognize a set of context free languages like {anbn|n belongs to N}

8. Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Add
View Answer

Answer: a
Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO principle, which states its rule as: Last In First Out.

9. A string is accepted by a PDA when
a) Stack is not empty
b) Acceptance state
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: b
Explanation: When we reach the acceptance state and find the stack to be empty, we say, the string has been accepted by the push down automata.

10. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Present state and Input Symbol
d) None of the mentioned
View Answer

Answer: c
Explanation: The next operation is performed by PDA considering three factors: present state,symbol on the top of the stack and the input symbol.

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

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.