Regex -> DFA question

Regex -> DFA question


bkubesh <bkubesh@earthlink.net> 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
completely.


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: uday@cs.unipune.ernet.in
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 :http://cs.unipune.ernet.in/~uday

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