Regex -> DFA question

Uday Khedkar <>
1 Apr 2000 14:03:09 -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: Uday Khedkar <>
Newsgroups: comp.compilers
Date: 1 Apr 2000 14:03:09 -0500
Organization: Compilers Central
References: 00-03-062
Keywords: lex, DFA, question

Regex -> DFA question

bkubesh <> writes :

>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

That's not quite correct. When you say (R1 | R2) you match either R1
or R2 (or both in case R1 == R2). There is no concept of "changing"
the track. If you start matching R1 in such way that the string you
matched cannot begin R2, then you continue matching R1 by ignoring R2

So the input provided above does not belong to the language (R1|R2).

You can refer to any book on formal languages and automata theory for
more details. (I studied from the classical book by Hopcroft and Ullman.)

Uday Khedker.

Dr. Uday Khedker email:
Reader phone: 91 (20) 565 7812 (Office)
Department of Computer Science 91 (20) 565 0794 (Office)
University of Pune 91 (20) 565 7206 (Res.)
Pune 411 007, India. url :

Post a followup to this message

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