Push Down Automata Practice Questions

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$ ?

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 ___________

Which one of the following is FALSE?

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?

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?

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

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?

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?

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)?

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

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?

Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata?

Which of the following conversions is not possible (algorithmically)?

Consider the NPDA $\left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \perp, F =\left \{ q_{2} \right \} \right \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?

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?

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 \}$, and $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 ___________

Consider the pushdown automaton $\text{(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 $\epsilon, X$ is a stack symbol, and $\gamma$ is a string of stack symbols, represents the fact that in state $u$, the $\text{(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 $\text{(PDA)}$ accepts by empty stack. Which one of the following options correctly describes the language accepted by $P ?$

A push down automation (pda) is given in the following extended notation of finite state diagram: The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form $d$, $s/s'$ where $d$ is the input symbol read and $s, s'$ are the stack contents before and after the move. For example the edge labeled $1, s/1.s$ denotes the move from state $q_0$ to $q_0$ in which the input symbol $1$ is read and pushed to the stack.