Can someone help me to construct a deterministic PDA for the following language:

$L = \{0^n1^m | n \geq m$ and $m,n \geq 0 \}$

Here is my suggestion : the states are z0,z1,z2 , z0 is final state , for the empty string , z1 should also be finate state :

enter image description here


Since you are confused, here are four hints to get you going. You will still have to think through the machine, but here are some of the big pieces:

  1. Push a marker onto the stack that will tell you where the bottom of the stack is. (Let's say, $\$$)
  2. Every time you find an $0$, push a symbol (let's say, $p$) onto the stack.
  3. When you finally find an $1$, stop pushing. Start popping off $p$s.
  4. If you reach the $\$$ before you've reached the end of your $1$s, then you've broken the $n \geq m$ condition.
  • $\begingroup$ what do you mean : every time you find an n ? everytime 0 has been read ? $\endgroup$ – Hans Christian Jun 12 '17 at 18:17
  • $\begingroup$ I have a suggestion . Can you please see it and give me a feedback ? $\endgroup$ – Hans Christian Jun 12 '17 at 18:40
  • $\begingroup$ I added my suggestion in my question $\endgroup$ – Hans Christian Jun 12 '17 at 18:58
  • $\begingroup$ Make an $\epsilon$ transition (some professors will call it a $\lambda$ transition) for putting in your $\$$, because it is just a marker of the starting point of the stack - no need to eat any input yet. Also, you do not need to push or pop on every action. Use $\epsilon$ whenever you do not wish to push (or pop). $\endgroup$ – Ben I. Jun 12 '17 at 19:14
  • $\begingroup$ I'm not quite sure if I understand u . Whats is this ϵ transition and where to put it ? And is my DPDA right ? $\endgroup$ – Hans Christian Jun 12 '17 at 19:25

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.