0
$\begingroup$

As I know $L=\{w\in\{a,b\}^*\mid n_a(w)=n_b(w)\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following enter image description here

However, as you may know, in Sipser's format, the transition $$\varepsilon,$;\varepsilon$$ means that "don't read any thing from the input" and it doesn't mean "read $\varepsilon$ from the input". In Sipser's format this is a non-deterministic push down automata, since in deterministic one, we have that if there is a transition $$\varepsilon,$;\varepsilon$$ outgoing from the state $q_1$ then it must not be an outgoing transition $$a,$;a$ $$ from that state.

Could you please help me to draw a DPDA for that language in Sipser's format?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

I myself have found that DPDA as follows: enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ Good for you. $ $ $\endgroup$ Dec 11, 2020 at 0:22
  • 1
    $\begingroup$ OK. Seems you can actually merge states q2 and q3 into one? $\endgroup$ Dec 11, 2020 at 13:32
  • $\begingroup$ @Hendrik Jan, yes. I think you are right. $\endgroup$ Dec 12, 2020 at 11:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.