I am reading Theory of Computation by Peter Linz. The transitions for PDA uses $\epsilon$ as end marker for input string. For example if the final state is $q_1$ then the transition is written like $\delta(q_0,\epsilon,z)=(q_1,z)$.

Why don't they write the transition as $\delta(q_0,\$,z)=(q_1,z)$.

  • $\begingroup$ We want to have possibility to allow stack to become empty without going to final state. $\endgroup$ – Szymon Stankiewicz Nov 4 '17 at 17:02
  • 1
    $\begingroup$ $\epsilon$ is not a "marker". $\endgroup$ – rici Nov 4 '17 at 17:11
  • $\begingroup$ @rici I know it's not a marker. But they are treating it like a marker. $\endgroup$ – Kishan Kumar Nov 4 '17 at 17:18
  • $\begingroup$ @KishanKumar If they did that, it would be wrong. An $\varepsilon$-transition can trigger at any point in time, not only at the end of the input. $\endgroup$ – Raphael Nov 4 '17 at 19:16
  • $\begingroup$ $\$$ is the "bottom of stack" marker. You can't introduce "end of input" markers without changing the input language (making it prefix-free). $\endgroup$ – Raphael Nov 4 '17 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.