<p>Perhaps I found some relevant information in:</p>

<p><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-59136-5_3">Jean-Michel Autebert, Jean Berstel, Luc Boasson; Context-Free Languages and Pushdown Automata; Handbook of Formal Languages; 1997, pp 111-174</a></p>

<p>DPDAs without $\epsilon$-transitions are known as <em>realtime deterministic pushdown automata</em>.</p>

<p>They are less powerful than DPDAs, for example </p>

<p>$L = \{ a^n b^p c  a^n \mid p,n &gt; 0\} \cup \{ a^nb^pdb^p\mid p,n &gt; 0 \}$</p>

<p>is deterministic and can be recognized by a DPDA, but cannot be recognized by any <em>realtime</em> DPDA.</p>

<p>What you can do is eliminate <em>increasing</em> $\epsilon$-transitions:</p>

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

CC BY-SA 3.0
2015-08-16T16:32:54.213Z
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.
Phylliida
CC BY-SA 3.0
2015-08-16T21:47:15.323Z
@DanielleEnsign: googling around you can find some results about RDPDAs, for example the [equivalence problem is decidable](http://link.springer.com/article/10.1007%2FBF01074776). But I agree with you, they have not attracted much attention.
Marzio De Biasi
CC BY-SA 3.0
2015-08-14T23:35:15.007Z
2015-08-15T16:47:05.430Z
2015-08-15T16:47:05.430Z
Marzio De Biasi
<p>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?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-14T03:14:56.310Z
Okay. So is there a reason we only study ones with $\epsilon$ moves then?
Phylliida
CC BY-SA 3.0
2015-08-14T03:44:33.640Z
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.
Phylliida
CC BY-SA 3.0
2015-08-14T03:49:53.533Z
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?
Phylliida
CC BY-SA 3.0
2015-08-14T12:27:40.400Z
Sounds good to me.
Klaus Draeger
CC BY-SA 3.0
2015-08-14T15:29:45.523Z
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.
Michael Wehar
CC BY-SA 3.0
2015-08-14T15:32:24.420Z
I'm looking forward to the answer to this question.  :)
Michael Wehar
CC BY-SA 3.0
2015-08-14T17:31:29.103Z
You're right, $\{a^{2n}b^n\} $ *can* be recognized without $\epsilon$-moves! Good question!
Marzio De Biasi
<automata-theory><context-free>
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
Phylliida
# Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

(Asked by: username_0 on 2015-08-13)

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.

**Tags:** automata-theory, context-free

> **Comments:**
> **username_0**: Okay. So is there a reason we only study ones with $\epsilon$ moves then?  
> **username_0**: 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.  
> **username_0**: 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?  
> **username_1**: Sounds good to me.  
> **username_2**: 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.  
> **username_2**: I'm looking forward to the answer to this question.  :)  
> **username_3**: You're right, $\{a^{2n}b^n\} $ *can* be recognized without $\epsilon$-moves! Good question!  

---

## 1 answers

### Answer by username_3 on 2015-08-14. Score: 20 | Accepted answer

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](http://link.springer.com/chapter/10.1007%2F978-3-642-59136-5_3)

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: @DanielleEnsign: googling around you can find some results about RDPDAs, for example the [equivalence problem is decidable](http://link.springer.com/article/10.1007%2FBF01074776). But I agree with you, they have not attracted much attention.  

---

