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 ___________

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 ___________

50 | |

49 | |

101 | |

100 |

Question 1 Explanation:

Question 2 |

Which one of the following is FALSE?

There is a unique minimal DFA for every regular language | |

Every NFA can be converted to an equivalent PDA. | |

Complement of every context-free language is recursive. | |

Every nondeterministic PDA can be converted to an equivalent deterministic PDA. |

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?

Which one of the following is TRUE?

L=\{a^{n}b^{n}|m\geq 0\} is not accepted by any finite automata | |

L=\{a^{n}|n\geq 0\}\cup \{a^{n}b^{n}|m\geq 0\} is not accepted by any deterministic PDA | |

L is not accepted by any Turing machine that halts one very input | |

L=\{a^{n}|n\geq 0\}\cup \{a^{n}b^{n}|m\geq 0\} is deterministic context-free |

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?

Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?

10110 | |

10010 | |

01010 | |

01001 |

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

(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^lb^mc^n \mid l = m = n\} | |

\{a^l b^m c^n \mid l = m\} | |

\{a^lb^mc^n \mid 2l = m + n\} | |

\{a^lb^mc^n \mid m = n\} |

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^nb^nc^n \mid n \geq 0\} | |

\{a^lb^mc^n \mid l \neq m \text{ or } m \neq n\} | |

\{a^nb^n \mid n \geq 0\} | |

\{a^mb^n \mid m, n \geq 0\} |

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?

L(P) is necessarily \Sigma^{*} but N(P) is not necessarily \Sigma^{*}. | |

N(P) is necessarily \Sigma^{*} but L(P) is not necessarily \Sigma^{*}. | |

Both L(P) and N(P) are necessarily \Sigma^{*}. | |

Neither L(P) nor N(P) are necessarily \Sigma^{*} |

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

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

aaa | |

aabab | |

baaba | |

bab |

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

Context free | |

Regular | |

Deterministic context | |

Recursive |

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?

L_1 = L_2 | |

L_1 \supset L_2 | |

L_1 \subset L_2 | |

None |

Question 10 Explanation:

There are 10 questions to complete.

check question 8 in GO answer is bab

Thank you subaru natsuki,

We have updated the answer.