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 :


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
  • $\begingroup$ 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. $\endgroup$ – Klaus Draeger Oct 18 '13 at 13:06
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Denis Oct 18 '13 at 13:51
  • $\begingroup$ 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$. $\endgroup$ – Klaus Draeger Oct 18 '13 at 14:07
  • $\begingroup$ 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 ) ? $\endgroup$ – adi Oct 18 '13 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.