2
$\begingroup$

For the Pushdown Automata episilon transition $\epsilon$ which is shorthand for $\epsilon; \epsilon / \epsilon$, does this mean that at any point, regargless of if there is input or not, you can transition to the next state? Or does it only transition to the next state when there is no more input?

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

A PDA is always allowed to take $\epsilon$ transitions, just like an NFA. More generally, the PDA is not allowed to peek at anything beyond the current letter. It cannot tell whether it has finished reading the word or not. Whether it can take a transition or not depends only on the contents of the stack and, in the case of a transition "swallowing" an input symbol, on the next symbol in the input (if any).

| cite | improve this answer | | | | |
$\endgroup$

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.