2
$\begingroup$

After defining pushdown automaton in Sipser's book at p. 113:

enter image description here

at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following:

enter image description here

My question is about the part "If $a$ is $\epsilon$, the machine may make this transition without reading any symbol from the input." But in many examples in the book, it seems some $\epsilon$s which are in place of $a$ must be interpreted as an empty string to show that the pointer is reached to the end of input. For example in the following diagram, we must interpret the first $\epsilon$ in the label of the transition between $q_3$ and $q_4$ to an empty string which shows the end of input string:

enter image description here

Otherwise, it can accept $01^2$. Since, if we interpret $\epsilon,\$\to\epsilon$ as to make this transition from $q_3$ to $q_4$ without reading the second 1, then $01^2$ would be accepted.

Now my question is how a PDA decides if that $\epsilon$ is for moving without reading any symbol from input or that $\epsilon$ is an empty string?

$\endgroup$
2
  • $\begingroup$ Read the next page. On p. 114, Sipser specifically says that in an accepting computation, "an accept state occurs $at\ the\ input\ end.$" (emphasis mine) $\endgroup$ – Rick Decker Mar 28 '20 at 18:00
  • $\begingroup$ OK I understood what you mean. $\endgroup$ – AmHsnSharafi Mar 28 '20 at 18:21
1
$\begingroup$

Suppose that your PDA is reading $011$.

At the beginning, the PDA is at state $q_1$, and the stack is empty. The only move the PDA can make is to put $\$$ on the stack and to transition to state $q_2$.

Since the next symbol to be read is $0$, the only move the PDA can make now is the self-loop on $q_2$ which puts $0$ on the stack. The input is now $11$, and the stack is $0\$$ (top of stack first).

Since the next symbol to be read is $1$, the only move the PDA can make is to transition to $q_3$, erasing $0$ from the top of the stack. The input is now $1$, and the stack is $\$$.

Since the next symbol to be read is $1$, the PDA must move to $q_4$, erasing $\$$ from the stack. The input is still $1$, and the stack is empty.

At this point, the PDA is stuck. It cannot make any move. However, it hasn't read all the input yet. We conclude that there is no accepting computation for this input, and so the PDA doesn't accept $011$.

$\endgroup$
5
  • $\begingroup$ Your answer is not true since after a symbol is read by a PDA, it can't be read again and it is not necessary to put it in stack (as you can see in some examples a machine may read a symbol but doesn't change the stack). $\endgroup$ – AmHsnSharafi Mar 28 '20 at 16:02
  • $\begingroup$ I guess we will have to disagree... $\endgroup$ – Yuval Filmus Mar 28 '20 at 17:06
  • $\begingroup$ @Rick Decker I disagree with what is written in 5th paragraph "The input is still 1" and what is written in 6th paragraph " it hasn't read all the input yet." I mean after machine read the last 1, why should it be waiting to read it again? $\endgroup$ – AmHsnSharafi Mar 28 '20 at 18:06
  • $\begingroup$ The machine never gets a chance to read the last 1. The transition from $q_3$ to $q_4$ is an $\epsilon$-transition, meaning no input is read at all. So if the remaining input had been $1$ prior to that transition, it remains $1$ even after transitioning. $\endgroup$ – Yuval Filmus Mar 28 '20 at 18:11
  • $\begingroup$ Thanks. I understood what you mean. $\endgroup$ – AmHsnSharafi Mar 28 '20 at 18: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.