Confusion about Definition of DPDA and $\epsilon$-move

Question

The DPDA definition is from sipser's book, and it mentions that the following PDA can convert to DPDA.

I tried it, then I confused the definition!

By definition, I could construct these

$\delta(q_1,\epsilon,\epsilon)=(q_2,\$) $

and because of "exactly one of the values"

$\delta(q_1,0 ,0 \text{ or } \$ \text{ or } \epsilon) = \varnothing$

$\delta(q_1,1 ,0 \text{ or } \$ \text{ or } \epsilon) = \varnothing$

$\delta(q_1,\epsilon ,0 \text{ or } \$ ) = \varnothing$

---

However, how about $\delta(q_1,\epsilon,\epsilon)$ , when I handle the $\{ 0^n1^n|n=0 \}$ ?

Does it means we can stop at two states $q_1,q_2$ with same string?

1. to stop at the $q_1$ is from no input string
2. to stop at the $q_2$ is from no input string, but $\epsilon$-move

And is it "deterministic" ?

Or why can definition allow $\delta(q,\epsilon,\epsilon)$?

Doesn't it break "deterministic" ?

---

Could I think that it finally stops at $\{q1, q2 \}$, and it at least contains one accept states $q1$ , so we accept it ?

---

Hence, by omitting the intermediate steps, I also can construct

$\delta(q_4,\epsilon ,\epsilon ) = q_r$, where $q_r$ is non-accept state with $\delta(q_r,\epsilon ,\epsilon ) = q_r$,

then all done.

Answer 1

The deterministic concept in pushdown automata means that next move of automata is determined uniquely.

This concept contains two points. First, there are no multiple choices in reading an alphabet from the input. For example, you should not have both of following rules is your transition rule

$$\delta(q,a,\alpha)=(p,\beta), \delta(q,\epsilon, \alpha)=(p',\gamma),$$

because you either can choose the first rule (that is $\delta(q,a,\alpha)=(p,\beta)$ ) read the $a$ then go to next state, or you can choose the second one (that is $\delta(q,\epsilon, \alpha)=(p',\gamma)$ ) do some other job before reading $a$ by $\epsilon$-transition. In the other words your choice in reading $a$ is not unique.

The second point of the definition is that you should exactly know what to do when you are reading an alphabet. Pay attention that the definition says $$\forall q\in Q, a\in \Sigma, x\in \Gamma,$$ which means there should be no ambiguity when you read an alphabet. For example, in above state diagram, one of the undefined rules is $\delta(q_3,0,x)$, where $x\in \Gamma$. Of course, this undefined rule is not important in our intuition that the PDA works correctly, but if we want to satisfy the definition of DPDA, then we should not let machine crash in the middle of reading an input. In the other words, the DPDA should read all characters of its input, then stop either in final state or non-final state.

I hope the above explanations help you in understanding Deterministic pushdown automata.

Now let's take a look at your first question. You've asked is it possible to stop at two states with the same string? The answer is no. I want to draw your attention to this part of definition again that says $\forall q\in Q, a\in \Sigma, x\in \Gamma.$ You missed the second point in the concept of determinism in the definition, that is you should define the rule $\delta(q_2,\epsilon,\$)$ for your DPDA. If we define $\delta(q_2,\epsilon,\$)=(\epsilon,q_4)$ and assume $q_4$ be the only final state, then the problem you arose will be solved.

To answer your second question, the definition allows $\delta(q,\epsilon,\epsilon)$ mostly because of the first transition rule. You will find some different definition for DPDA in some other books which handle the first transition rule in some other ways. For example, some people agree that at the beginning we already have $\$$ on the stack.

your statement about $q_4$ is ok.