2
$\begingroup$

I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q_1,\epsilon, Z_0)\to(q_2,Z_0)$, where $q_2$ is the final state.

In DFAs we don't consider $\epsilon$ transitions, while in PDAs we do include them. Why?

$\endgroup$
  • $\begingroup$ It's a question of definition; $\epsilon$ transitions can be eliminated from PDAs in the same way they are eliminated from $\epsilon$-DFAs. $\endgroup$ – Yuval Filmus Mar 10 '14 at 2:37
  • $\begingroup$ @YuvalFilmus Oh We have $\epsilon$-DFA! $\endgroup$ – user5507 Mar 10 '14 at 4:59
  • $\begingroup$ @YuvalFilmus: As far as I know, there is no standard construction for elimination $\varepsilon$-transitions from PDA other than going via grammars. Do you know one? $\endgroup$ – Raphael Mar 10 '14 at 9:07
  • $\begingroup$ @Raphael You're right, they are more powerful in PDAs because of the stack. $\endgroup$ – Yuval Filmus Mar 10 '14 at 12:04
5
$\begingroup$

There are definitely definitions of DFA that allow $\varepsilon$-transitions. Arguably, they are not very useful for three reasons.

  1. They don't add computational power.
  2. If you have them, you have to require (for DFA) that every $\varepsilon$-transition is the only transition leaving its source state.
  3. Everything you might want to do with them (say, prove closure of regular languages against concatenation) can be done by using NFA and determinising.

Because they do have use in proofs, they are usually included in the definition of NFA, though. For example, consider translating regular expressions into NFA.

In PDAs, $\varepsilon$-transitions can be used to deal with stack content without consuming any input. Even in DPDA there can be multiple choices in any given state, depending on stack content. So they are useful here for constructing PDA and are thus usually included in the definition.

$\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.