NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions.

However, NFA's with $\epsilon$ transitions could be converted to those without any $\epsilon$ transitions and hence they can be made to halt.

I was wondering if this is possible even for the case of NPDA's.

Is there a canonical epsilon-free form for PDAs

  • $\begingroup$ What's your definition of 'halt'? Or maybe halting is a tangent and you don't actually care about halting; you only care about epsilon-free versions of PDAs? $\endgroup$ – D.W. Apr 12 '16 at 19:57

This effect I would not consider this a "halting problem" but there is a point here. A pushdown automaton can end its computation in an unbounded sequence of $\varepsilon$-moves. This behaviour can be avoided for general PDA, indeed. For each PDA there is an equivalent PDA without $\varepsilon$-moves. This is equivalent to Greibach Normal Form for grammars.

For deterministic PDA, DPDA, the situation is different. We would like to avoid this unbounded behaviour, in particular for the construction of the complement of the language of the DPDA. As you might know DPDA are closed under complement. Quite involved constructions can avoid infinite computations, but we cannot avoid $\varepsilon$-moves.

The language $\{ a^mb^nc^n \mid m,n\ge 1\} \cup \{ a^mb^nd^m \mid m,n\ge 1\}$ can be accepted by a DPDA but it has to use $\varepsilon$-moves.

| cite | improve this answer | |

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.