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 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 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 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 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 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 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 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 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 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
There are 10 questions to complete.

2 thoughts on “Push-down Automata”

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.