0
$\begingroup$

Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works?

we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols $\{S,A,B \}$, start state $q_0$, accept state $q_3$, we have rules as following: $q_0$ accepts nothing and push $S$ onto stack to $q_1$

$q_1$ reads $a$ and pops $B$, remain in $q_1$

$q_1$ reads $a$ and pushes $A$, remain in $q_1$

$q_1$ reads $b$ and pushes $BB$, remain in $q_1$

$q_1$ reads $b$ and pops$AA$, remain in $q_1$

$q_1$ reads $b$ and pops$A$ and pushes $B$, remain in $q_1$

$q_1$ reads nothing and pops $B$, go to $q_2$

$q_2$ reads nothing and pops $B$, remain in $q_2$

$q_2$ reads nothing and pops $S$, go to $p_3$

$\endgroup$
  • $\begingroup$ I think in transition rule 3 you may want to include which stack symbol should be there on stack top. $\endgroup$ – Vimal Patel Oct 26 '19 at 4:35
  • $\begingroup$ This is NPDA, the situation you mentioned will not go to the final state $\endgroup$ – Joe Oct 26 '19 at 4:36
  • 3
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. $\endgroup$ – D.W. Oct 26 '19 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.