Re: Regexps from DFA

G Venkatesha Murthy <gvmt@csa.iisc.ernet.in> 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
reviewing.


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
Waterloo.


--------------------


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 comp.compilers page.
Search the comp.compilers archives again.