Re: a problem on building a regular expression

On Fri, 9 Mar 2007, Michael wrote:

I agree - the DFA is quite simple. I couldn't remember how to convert
that to a regular expression, even though I know it should be
possible. Could you point me to a reference?

Indeed I do not know a *practical* reference, so I have written my own
recipe. Unfortunately, it is in German:

http://www.lrz-muenchen.de/services/schulung/unterlagen/regul/regul-13.html#publish4.2.1.0.0.0

It is a part of longer paper. In the cited subpage, there are two DFAs.
The first one transforms quite obviously to a regular expression, the
steps are explained in points 1 to 3 in the text. I guess I need not
explain that.

For the DFA in the second sketch, there is no obvious transformation. The
trick is then to split a state, C, into an entry-only state, C0, and an
exit-only state, C1. Then one considers separately the paths from the
initial state, A, to the final state, E, that do not pass by C, then the
paths from A to C1 (these are the paths in the original DFA from A to C
that do not pass by C), the paths from C0 to E, and the paths from C0 to
C1. Then the results are combined into a single regular expression.

There is one more example, to wit the decimal numbers divisible by 3,
which require more than one such state-split:

http://www.lrz-muenchen.de/services/schulung/unterlagen/regul/regul-14.html#publish4.3.2.0.0.0

It has quite some similarity with the problem at hand.

--
Helmut Richter
.

Relevant Pages

  • Re: VB Regular Expression in Outlook?
    ... add a reference to the Microsoft VBScript Regular Expressions 5.5 library. ... Author of Microsoft Outlook 2007 Programming: ... I found that Regular Expression can also be used according to a post by Sue ... I was not able to find a reference within MSDN for VB Outlook Regular ...
    (microsoft.public.outlook.program_vba)
  • Re: Regular Expressions in Visual Studios Find & Replace
    ... I found that Help reference on regular expressions, but I missed that tag stuff ... |> Could someone give me a very simple regular expression for Visual Studio's ... I want to use something I can use in VS interactave search/replace, ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Regular Expressions in Visual Studios Find & Replace
    ... I found that Help reference on regular expressions, but I missed that tag stuff ... |> Could someone give me a very simple regular expression for Visual Studio's ... I want to use something I can use in VS interactave search/replace, ...
    (microsoft.public.vstudio.general)
  • Re: Why does Tie::Simeple (scalar) work without real local data?
    ... On 12/04/2006 06:03 PM, John W. Krahn wrote: ... And a qr// object is just a reference after all: ... tie my $incr, 'Tie::Simple', $sb, ... The regular expression is somehow changed, and it seems to be storing my value in it, but compiled regular expressions can't contain numbers--can they? ...
    (comp.lang.perl.modules)
  • 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)