|Regexps from DFA firstname.lastname@example.org (G Venkatesha Murthy) (1997-02-02)|
|Re: Regexps from DFA email@example.com (1997-02-03)|
|Re: Regexps from DFA firstname.lastname@example.org (1997-02-03)|
|Re: Regexps from DFA email@example.com (1997-02-07)|
|Re: Regexps from DFA firstname.lastname@example.org (1997-02-07)|
|Re: Regexps from DFA email@example.com (Philip Lijnzaad) (1997-02-07)|
|From:||firstname.lastname@example.org (Allyn Dimock)|
|Date:||3 Feb 1997 13:46:39 -0500|
|Organization:||Aiken Computation Lab, Harvard University|
G Venkatesha Murthy <email@example.com> writes:
|> We recently had a post asking what regexp would describe a given set
|> of strings. Of course, there's the easiest one - one exact match for
|> each string - but we are interested in something "proper". I suppose
|> that answer lies in being able to extract a regexp from a DFA. How do
|> we get a regexp for a language accepted by a given DFA? Once we do
|> that, it is straight forward to obtain the regexp describing the set
|> of strings.
The idea of deriving a regular expression from a DFA is worth
Notice that the constructions used in proving the equivalence of
finita automata and regular espressions are constructive.
Lewis & Paparimitriou -- Elements of the theory of computation thm
2.5.1, example 2.5.2 pages 69 - 73
Hopcroft & Ullman -- Introduction to Automata Theory, Languages and
Computation Thm 2.4 and example 2.13 pages 33 - 35
Also see "Expression Automata" by J.A. Brzozowski, University of
Are the regular expressions generated byt these algorithms in any
sense "proper" I doubt it. The regular expressions that I have seen
generated by these algorithms are often simplifiable by standard
regular expression identities.
Is this process worthwhile? If you just go from a finite set of
strings to a NDFA by the standard construction and then immediately
apply Brzozowski's algorithm you end up with the union of the initial
strings plus the odd concatenation with the Kleene-* of the empty
string here and there.
If you create a NDFA, use the subset construction to convert to a DFA,
and minimize the DFA you end up (in worst case exponential time) with
a regular expression that is generally hard to read...
-- Allyn Dimock
Return to the
Search the comp.compilers archives again.