# Push-down Automata

 Question 1
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form,

where $p,q \in Q \; a \in \sigma \cup \{ \epsilon \} ,\;X,Y, \in \Gamma \cup \{ \epsilon \}$, represents

$(q,Y) \in \delta(p,a,X)$

Consider the following pushdown automaton over the input alphabet $\Sigma = \{a,b\}$ and stack alphabet $\Gamma = \{ \#, A\}$.

The number of strings of length 100 accepted by the above pushdown automaton is ___________
 A 50 B 49 C 101 D 100
GATE CSE 2021 SET-1   Theory of Computation
Question 1 Explanation:
 Question 2
Which one of the following is FALSE?
 A There is a unique minimal DFA for every regular language B Every NFA can be converted to an equivalent PDA. C Complement of every context-free language is recursive. D Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
ISRO CSE 2017   Theory of Computation
Question 2 Explanation:
 Question 3
Consider the transition diagram of a PDA given below with input alphabet $\Sigma$={a,b} and stack alphabet $\Gamma$={X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?
 A $L=\{a^{n}b^{n}|m\geq 0\}$ is not accepted by any finite automata B $L=\{a^{n}|n\geq 0\}\cup \{a^{n}b^{n}|m\geq 0\}$ is not accepted by any deterministic PDA C L is not accepted by any Turing machine that halts one very input D $L=\{a^{n}|n\geq 0\}\cup \{a^{n}b^{n}|m\geq 0\}$ is deterministic context-free
GATE CSE 2016 SET-1   Theory of Computation
Question 3 Explanation:
 Question 4
Consider the NPDA $\langle Q=\{q_{0},q_{1},q_{2}\},$ $\Sigma =\{0,1\},$ $\Gamma =\{0,1,\perp \},\delta ,q_{0},\perp ,$ $F=\{q_{2}\} \rangle$, where (as per usual convention) Q is the set of states, $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, $\delta$ is the state transition function, $q_{0}$ is the initial state, $\perp$ is the initial stack symbol, and $F$ is the set of accepting states. The state transition is as follows:

Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
 A $10110$ B $10010$ C $01010$ D $01001$
GATE CSE 2015 SET-1   Theory of Computation
Question 4 Explanation:
 Question 5
Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet $\{Z_0, X\}$ where $Z_0$ is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition $(s, b, X) \rightarrow (t, XZ_0)$ means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols $Z_0$ and X (in that order) on the stack.
$(s, a, Z_0) \rightarrow (s, XXZ_0)$
$(s, \epsilon, Z_0) \rightarrow (f, \epsilon)$
$(s, a, X) \rightarrow (s, XXX)$
$(s, b, X) \rightarrow (t, \epsilon)$
$(t, b, X) \rightarrow (t,\epsilon)$
$(t, c, X) \rightarrow (u, \epsilon)$
$(u, c, X) \rightarrow (u, \epsilon)$
$(u, \epsilon, Z_0) \rightarrow (f, \epsilon)$
The language accepted by the PDA is
 A $\{a^lb^mc^n \mid l = m = n\}$ B $\{a^l b^m c^n \mid l = m\}$ C $\{a^lb^mc^n \mid 2l = m + n\}$ D $\{a^lb^mc^n \mid m = n\}$
GATE IT 2006   Theory of Computation
Question 5 Explanation:
 Question 6
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?
 A $\{a^nb^nc^n \mid n \geq 0\}$ B $\{a^lb^mc^n \mid l \neq m \text{ or } m \neq n\}$ C $\{a^nb^n \mid n \geq 0\}$ D $\{a^mb^n \mid m, n \geq 0\}$
GATE IT 2006   Theory of Computation
Question 6 Explanation:
 Question 7
Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be $\Sigma$. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?
 A L(P) is necessarily $\Sigma^{*}$ but N(P) is not necessarily $\Sigma^{*}$. B N(P) is necessarily $\Sigma^{*}$ but L(P) is not necessarily $\Sigma^{*}$. C Both L(P) and N(P) are necessarily $\Sigma^{*}$. D Neither L(P) nor N(P) are necessarily $\Sigma^{*}$
GATE IT 2005   Theory of Computation
Question 7 Explanation:
 Question 8
Let $M=(K, \Sigma, \Gamma, \Delta, s, F)$ be a pushdown automaton, where
$K=(s, f), F=\{f\}, \Sigma=\{a, b\}, \Gamma=\{a\} \text { and }$
$\Delta=\{((s, a, \epsilon),(s, a)),((s, b, \epsilon),(s, a)),((s, a, a),(f, \epsilon)),((f, a, a),(f, \epsilon)) ((f, b, a),(f, \epsilon))\}$
Which one of the following strings is not a member of L(M)?
 A aaa B aabab C baaba D bab
GATE IT 2004   Theory of Computation
Question 8 Explanation:
 Question 9
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
 A Context free B Regular C Deterministic context D Recursive
GATE CSE 2002   Theory of Computation
Question 9 Explanation:
 Question 10
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?
 A $L_1 = L_2$ B $L_1 \supset L_2$ C $L_1 \subset L_2$ D None
GATE CSE 1999   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.

### 2 thoughts on “Push-down Automata”

1. check question 8 in GO answer is bab