Register

GO Classes DPP | TOC|PDA

309 views
2 2 votes

Consider the Pushdown Automaton (PDA) specified below, which accepts by final state.

  • States $Q:\left\{q_0, q_1, q_2\right\}$
     
  • Input $\Sigma:\{a, b\}$
     
  • Stack $\Gamma:\left\{A, Z_0\right\}\left(Z_0\right.$ is the initial stack symbol)
     
  • Start State: $q_0$
     
  • Final State $F:\left\{q_2\right\}$

The state transition function $\delta$ is given by the following diagram. The notation $x, Y \rightarrow \alpha$ means "on input $x$, pop $Y$, and push $\alpha$ ".

 

 

 

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

  1. $b$
     
  2. $b a$
     
  3. $b b$
     
  4. $b b a$

2 Answers

2 2 votes

This pda accepts $\left\{a^{\wedge} n \cdot b^{\wedge} n \mid n>=0\right\}$


Hence C is correct

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | TOC...Next → · GO Classes DPP | TOC...
← Previous in category · GO Classes DPP | TOC...Next in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

3 3 votes
1 1 answer
433
433 views
GO Classes asked Nov 1, 2025
433 views
GO Classes DPP | TOC|DECIDABILITY
Let $\langle M\rangle$ denote the standard encoding of a machine $M$. Consider the following languages.$L_1=\{\langle A\rangle \mid A$ is a DFA and $|L(A)| \geq 100\}$ $L...
3 3 votes
2 2 answers
282
282 views
GO Classes asked Nov 1, 2025
282 views
GO Classes DPP | TOC|GRAMMAR
Consider the alphabet $\Sigma=\{a, b\}$, the null/empty string $\epsilon$, and the set of strings $S, A$, and $B$ generated by the corresponding non-terminals of a regula...
4 4 votes
1 1 answer
247
247 views
GO Classes asked Nov 1, 2025
247 views
GO Classes DPP | TOC| GRAMMAR
$$\begin{gathered}S \rightarrow a S|b B| \epsilon \\B \rightarrow b S \mid a B\end{gathered}$$The Myhill-Nerode equivalence classes for the language generated by this gra...
2 2 votes
4 4 answers
503
503 views
GO Classes asked Nov 1, 2025
503 views
GO Classes DPP | TOC|RE
Which one of the following languages over the alphabet $\{a, b\}$ is described by the regular expression:$$(a+b)^* a(a+b)^* a(a+b)^* ?$$The set of all strings containing ...