Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!usc!snorkelwacker!spdcc!ima!esegue!compilers-sender
From: worley@compass.com (Dale Worley)
Newsgroups: comp.compilers
Subject: Regular expressions & finite automata.
Keywords: lex, DFA
Message-ID: <9008231529.AA26343@sn1987a.compass.com>
Date: 23 Aug 90 15:29:32 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: worley@compass.com (Dale Worley)
Organization: Compilers Central
Lines: 22
Approved: compilers@esegue.segue.boston.ma.us
In-Reply-To: John R. Levine's message of Wed, 22 Aug 90 12:45:44 EDT <9008221245.AA11458@esegue.segue.boston.ma.us>


   [There are many equivalent DFAs that a regular expression can translate to,
   and vice versa.  After all, any regular expression can be written in
   infinitely many equivalent ways, e.g. a(b|c) vs. ab|ac, or to be really
   pedantic, x vs. (x|x) vs. (x|x|x) ... -John]

However, all DFAs for a given regular language can be derived from the
minimal DFA (the one with the fewest states that accepts that
language) by turning single states into sets of equivalent states.

Dale Worley		Compass, Inc.			worley@compass.com
--
My favorite was an example in Dijkstra's classic "A Discipline of
Programming" where he claimed that he hadn't submitted his program
to operational testing since it had been created using a discipline
that guaranteed it would be correct.  Naturally, there were a couple
of bugs in it! -- Doug Gwyn
[Dale mentioned in a separate note that Aho and Ullman's books tell this
and much more about DFAs and regular expressions. -John]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.