Removing $\epsilon$ transitions in a NPDA

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

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.

StackExchange Computer Science Q#55875, answer score: 5