Regex -> DFA question

bkubesh <>
11 Mar 2000 13:12:50 -0500

          From comp.compilers

Related articles
Regex -> DFA question (bkubesh) (2000-03-11)
Regex -> DFA question (Uday Khedkar) (2000-04-01)
Re: Regex -> DFA question (Chris F Clark) (2000-04-03)
| List of all articles for this month |

From: bkubesh <>
Newsgroups: comp.compilers
Date: 11 Mar 2000 13:12:50 -0500
Organization: Road Runner - Texas
Keywords: DFA

My question is very similiar to Paul Johnston's question about a month
ago, but with a twist. When constructing multiple Regex's how does one
handle the following case:

R1 | R2

Where R1=(ab.*cd) and R2=(gh.*ij)

Suppose we process the following input: abghxxcidij

After we have processed the starting sequences, it would seem as though
we need to be able to "cross track" between the two expressions in the
OR. How do I handle this case for R2 in the above example. If I first
construct the NFA using backtracking epsilon transitions and convert to
DFA, I dont see how the DFA will handle this case correctly. It will be
stuck in R1 waiting for a 'd' when it should have accepted the input in

It seems very likely this problem has already been solved. Am I missing
Thanks in advance,

> Paul Johnston wrote:
> The problem I have now is that I am failing to translate a *set* of
> regular expression into a lexical analyzer (rather than just one
> regular expression). If I had built this tool going from regex to NFA

> to DFA, rather than straight to a DFA, then this would be solved by
> constructing a new start state s0 and linking to each NFA pattern with

> an epsilon-transition, as shown on the diagram on page 130.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.