Re: Create DFA from regular expression?

"Paminu" <jadajada@xxxxxxx> wrote in message
news:dli8r2$osu$1@xxxxxxxxxxxxxxxxxxxx
> Is it possible to create a DFA directly from a regular expression or is it
> necessary first to create the NFA?

You can create it directly from the regular expression using "derivatives",
where the derivative of a regular expression R w.r.t. some symbol 'a',
written D_aR, is the expression that matches all strings x such that R
matches ax. A DFA that accepts R will have a transition on 'a' from the
start state to a state that accepts D_aR.

Let \ be the expression matching nothing, and let E be the expression
matching only the empty string.

For all symbols a and b, and expressions R and S:

D_a\ = \
D_aE = \
D_aa = E
D_ab = \
D_a(R|S) = D_aR | D_aS
D_aR* = (D_aR)(R*)
D_a(RS) = (D_aR)S | (D_aS) if R matches the empty string, and just (D_aR)S
otherwise.

Using these with some simplification rules is often the easiest way to find
DFAs by hand. If you're programming it, though, all that symbolic stuff is
a pain, and it's much easier just to make the NFA first and convert it.

--
Matt




.

Relevant Pages

  • Re: Create DFA from regular expression?
    ... >> Is it possible to create a DFA directly from a regular expression or is ... >> it necessary first to create the NFA? ... A DFA that accepts R will have a transition on 'a' from the ... and it's much easier just to make the NFA first and convert it. ...
    (comp.theory)
  • Re: Henry Spencers "Tcl" Regex Library
    ... finite-state automata", because their machine is mostly like a DFA, ... but with a few NFA portions (and I mean true NFA not nonregular/regexp ... regular expression but doesn't describe a regular language. ... They probably use the hybrid term because the machine executes a DFA ...
    (comp.compilers)
  • Re: Create DFA from regular expression?
    ... >> Is it possible to create a DFA directly from a regular expression or is it ... A DFA that accepts R will have a transition on 'a' from the ... The simplification rules are important. ... and it's much easier just to make the NFA first and convert it. ...
    (comp.theory)
  • Create DFA from regular expression?
    ... Is it possible to create a DFA directly from a regular expression or is it ... necessary first to create the NFA? ... Prev by Date: ...
    (comp.theory)
  • Re: regular expressions and DFAs
    ... The regular expression: ... Every NFA has at least one DFA that accepts the same language. ... Look up "Subset Construction" for a proof of this, and also an algorithm to convert between NFAs and DFAs. ...
    (comp.theory)