Regular expressions & finite automata.

worley@compass.com (Dale Worley)
Thu, 23 Aug 90 11:29:32 EDT

          From comp.compilers
Related articles
Regular expressions & finite automata. mph@inmos.com (Mike Harrison) (1990-08-15)
Regular expressions & finite automata. worley@compass.com (1990-08-23)
Re: Regular expressions & finite automata. hankd@dynamo.ecn.purdue.edu (1990-08-24)
| List of all articles for this month |
Newsgroups: comp.compilers
From: worley@compass.com (Dale Worley)
In-Reply-To: John R. Levine's message of Wed, 22 Aug 90 12:45:44 EDT <9008221245.AA11458@esegue.segue.boston.ma.us>
Keywords: lex, DFA
Organization: Compilers Central
Date: Thu, 23 Aug 90 11:29:32 EDT

      [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]
--

Post a followup to this message

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