17
$\begingroup$

In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\epsilon$ moves aren't allowed, and the stack can only be modified once after each symbol read, are the resulting automata equal to power to DPDAs?

There may be something trivial I am missing with regards to using the powerset of $\Gamma$ as your new $\Gamma$, allowing you to "compress" $\epsilon$ moves into the equivalent automaton without them, similar to how you can compress $\epsilon$ moves in a DFA. Just it seems that such a conversion is not as trivial as for DFAs, and I'm not sure it's even possible.

So are the two equivalent in power? I'm just asking because everyone seems to assume that DPDAs have $\epsilon$ moves and I'm wondering why that assumption exists, since it seems like a more complex model.

Improve this question
$\endgroup$
7
  • $\begingroup$ Okay. So is there a reason we only study ones with $\epsilon$ moves then? $\endgroup$
    – Phylliida
    Commented Aug 14, 2015 at 3:14
  • 1
    $\begingroup$ So I just realized you actually can recognize $L=\{a^{2n}b^n\}$. You simply begin in an accept state, then upon reading the first $a$, you push & onto the stack, and upon reading the second $a$ you push # onto the stack. After that, you write an $a$ to the stack for every other $a$ you read, starting with the $a$ you read after pushing # to the stack. $\endgroup$
    – Phylliida
    Commented Aug 14, 2015 at 3:44
  • $\begingroup$ Then, if you read a $b$ while knowing that you read a odd number of $a$'s you reject (sit in a stuck state), otherwise you go into another state and push an $a$ off the stack. You repeat this for every $b$ read. If eventually while parsing a $b$, # is at the top of the stack instead of an $a$, enter an accept state. Then enter a reject state if any more symbols are read. In any case that is different than the ones outlined above, enter a reject state. Does that work? $\endgroup$
    – Phylliida
    Commented Aug 14, 2015 at 3:49
  • $\begingroup$ Sounds good to me. $\endgroup$
    – Klaus Draeger
    Commented Aug 14, 2015 at 12:27
  • 1
    $\begingroup$ Correct me if I'm wrong, but I agree. I also believe that you can recognize $\{ a^{2n}b^{n} \}$ with a DPDA that always moves right on the input tape (never stopping). The only tricky part is making it finish on the final state. Acceptance for DPDA's can be tricky. $\endgroup$
    – Michael Wehar
    Commented Aug 14, 2015 at 15:29

1 Answer 1

Reset to default
20
$\begingroup$

Perhaps I found some relevant information in:

Jean-Michel Autebert, Jean Berstel, Luc Boasson; Context-Free Languages and Pushdown Automata; Handbook of Formal Languages; 1997, pp 111-174

DPDAs without $\epsilon$-transitions are known as realtime deterministic pushdown automata.

They are less powerful than DPDAs, for example

$L = \{ a^n b^p c a^n \mid p,n > 0\} \cup \{ a^nb^pdb^p\mid p,n > 0 \}$

is deterministic and can be recognized by a DPDA, but cannot be recognized by any realtime DPDA.

What you can do is eliminate increasing $\epsilon$-transitions:

Proposition 5.4: For any DPDA it is possible to construct a DPDA recognizing the same language such that any $\epsilon$-rule is decreasing.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Awesome, thanks! So this answers the first part of my question. The second part is - why don't we study these? Everyone seems focused on non-real-time ones and that seems odd to me. $\endgroup$
    – Phylliida
    Commented Aug 16, 2015 at 16:32
  • 2
    $\begingroup$ @DanielleEnsign: googling around you can find some results about RDPDAs, for example the equivalence problem is decidable. But I agree with you, they have not attracted much attention. $\endgroup$
    – Marzio De Biasi
    Commented Aug 16, 2015 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.