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


There are 5 questions to complete.

2 thoughts on “Push-down Automata”

Leave a Comment