Re: Create DFA from regular expression?

Matt Timmermans wrote:

> "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

Thanks!
.

Relevant Pages

  • Re: Create DFA from regular expression?
    ... > necessary first to create the NFA? ... You can create it directly from the regular expression using "derivatives", ... 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)