Re: Regexps from DFA

dimock@deas.harvard.edu (Allyn Dimock)
3 Feb 1997 13:46:39 -0500

          From comp.compilers

Related articles
Regexps from DFA gvmt@csa.iisc.ernet.in (G Venkatesha Murthy) (1997-02-02)
Re: Regexps from DFA anton@a0.complang.tuwien.ac.at (1997-02-03)
Re: Regexps from DFA dimock@deas.harvard.edu (1997-02-03)
Re: Regexps from DFA clark@quarry.zk3.dec.com (1997-02-07)
Re: Regexps from DFA mslamm@pluto.mscc.huji.ac.il (1997-02-07)
Re: Regexps from DFA lijnzaad@ebi.ac.uk (Philip Lijnzaad) (1997-02-07)
| List of all articles for this month |

From: dimock@deas.harvard.edu (Allyn Dimock)
Newsgroups: comp.compilers
Date: 3 Feb 1997 13:46:39 -0500
Organization: Aiken Computation Lab, Harvard University
References: 97-02-020
Keywords: lex, 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
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.