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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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