Re: Regexps from DFA (Allyn Dimock)
3 Feb 1997 13:46:39 -0500

          From comp.compilers

Related articles
Regexps from DFA (G Venkatesha Murthy) (1997-02-02)
Re: Regexps from DFA (1997-02-03)
Re: Regexps from DFA (1997-02-03)
Re: Regexps from DFA (1997-02-07)
Re: Regexps from DFA (1997-02-07)
Re: Regexps from DFA (Philip Lijnzaad) (1997-02-07)
| List of all articles for this month |

From: (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 <> 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

Post a followup to this message

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