# Is it possible to simulate a regular expression using a single stack?

I understand that a regular expression can be converted to an equivalent DFA which can then be simulated. However, is it possible to simulate the regular expression directly with the aid of a stack ? I believe that by pushing the alphabets onto a stack and expanding any composite expression such as (r1.r2) into its constituent expressions one can parse against the regular expression but I am unable to figure out how to deal with the | operator . As an example of what I am thinking consider the following regular expression :

a.b.(c.d)*.e


The string abe can be parsed against the regular expression in the following way using a stack:

Stack:             alphabet action
|e|(c.d)*|b|a      a        match: pop off the stack
|e|(c.d)*|b        b        match: pop off the stack
|e|(c.d)*          e        composite element , expand
|e|(c.d)*|d|c      e        no match , but expanding from a composite under kleene closure , pop off
^
|e|(c.d)*|d        e        no match , but expanding from a composite under kleene closure , pop off
^
|e|(c.d)*          e        stack top not an alphabet, pop off
|e                 e        match : pop off from stack

• If you are willing to modify the expression, you should be able to push "|" operators outwards using the equivalences of Kleene algebra, such as $(u|v).w = (u.w)|(v.w)$ and $(u|v)^* = u^*.(v.u^*)^*$. You can then deal with any resulting top-level $|$ operators by checking the (finitely many) cases individually. – Klaus Draeger Oct 18 '13 at 13:06
• how do you distinguish between line 3 and line 6 ? do you use a memory state ? what is the precise model you are asking for ? Deterministic pushdown automaton with only one state ? – Denis Oct 18 '13 at 13:51
• I guess that is what the marking on the $(c.d)^*$ element is for. I still have to wonder how this approach would deal with expressions like $(a.b)^*.(a.c)^*$, when parsing an $a$. – Klaus Draeger Oct 18 '13 at 14:07
• Yes, I now realize that this would be equivalent to simulating a DPDA where I would have to keep track of expansions for "|" and "*" . In that case, for a given regular language, is it possible to mechanically construct a DPDA that would have fewer states than the DFA for the language (considering that certain operations such as concatenation can be handled by the stack ) ? – adi Oct 18 '13 at 14:24