Push Down automata:- Basic doubt

Question

I was reading CFG's and PDA's. I need to understand one basic point in that.I have solved some questions on final state acceptance by PDA.But in every answer,the string always end with epsilon(means that there is always a transition when string ends which by reading epsilon takes to final state and mostly it invloves checking that current stack TOP is same as initial symbol).

Do we assume that there is some end of string marker in PDA?I have not seen such thing in DFA/NFA.If the string ends,then there is no need to read epsillon in that,but what is the requirement for this in PDA?Or does this depends on the problem in context?

Answer 1

In general we do not assume that push-down automata have an end-of-string (or end-of-input) marker.

PDA have two modes of acceptance, with final state and with empty stack. Even when the automata are written for final state acceptance it is helpful in the design to check that the stack is empty. That ensures no data is unprocessed.

The PDA on wikipedia for the language $\{0^{n}1^{n}\mid n\geq 0\}$ has transitions: $(p,0,Z,p,AZ)$, $(p,0,A,p,AA)$, $(p,\epsilon ,Z,q,Z)$, $(p,\epsilon ,A,q,A)$, $(q,1,A,q,\epsilon )$, and $(q,\epsilon ,Z,r,Z)$. Initial state $p$ and final state $r$. This indeed is of the form you describe.

The same language can be accepted without $\epsilon$-transitions at all.

$(p,0,Z,q,Z)$, $(q,0,Z,q,AZ)$, $(q,0,A,q,AA)$, $(q,1,A,r,\epsilon)$, $(q,1,Z,s,\epsilon)$, $(r,1,A,r,\epsilon)$, $(r,1,Z,s,\epsilon)$. Initial state $p$ and final states $p$ [to accept $\epsilon$] and $s$.