# construct a deterministic PDA for the language

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 :

## 1 Answer

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 ps. 4. If you reach the \$$ before you've reached the end of your$1$s, then you've broken the$n \geq m$condition. • what do you mean : every time you find an n ? everytime 0 has been read ? – Hans Christian Jun 12 '17 at 18:17 • I have a suggestion . Can you please see it and give me a feedback ? – Hans Christian Jun 12 '17 at 18:40 • I added my suggestion in my question – Hans Christian Jun 12 '17 at 18:58 • 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). – Ben I. Jun 12 '17 at 19:14
• I'm not quite sure if I understand u . Whats is this ϵ transition and where to put it ? And is my DPDA right ? – Hans Christian Jun 12 '17 at 19:25