# Push-down Automata

 Question 1
Consider the pushdown automaton (PDA) $P$ below, which runs on the input alphabet $\{a,b\}$, has stack alphabet $\{ \perp ,A\}$, and has three states $\{s,p,q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ , labelled $c/X/\gamma$ , where $c$ is an input symbol or , $X$ is a stack symbol, and $\gamma$ is a string of stack symbols, represents the fact that in state $u$, the PDA can read $c$ from the input, with $X$ on the top of its stack, pop $X$ from the stack, push in the string $\gamma$ on the stack, and go to state $v$. In the initial configuration, the stack has only the symbol $\perp$ in it. The PDA accepts by empty stack. Which one of the following options correctly describes the language accepted by $P$?
 A $\{ a^mb^n |1\leq m\text{ and }n \lt m \}$ B $\{ a^mb^n |0 \leq n \leq m \}$ C $\{ a^mb^n |0\leq m\text{ and } 0 \lt n \}$ D $\{ a^m |0\leq m \} \cup \{b^n|0 \leq n \}$
GATE CSE 2023   Theory of Computation
Question 1 Explanation:
 Question 2
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 2 Explanation:

 Question 3
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 3 Explanation:
 Question 4
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 4 Explanation:
 Question 5
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 5 Explanation:

There are 5 questions to complete.

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

1. check question 8 in GO answer is bab

• 