Path: utzoo!attcan!uunet!snorkelwacker!spdcc!ima!esegue!compilers-sender
From: mph@inmos.com (Mike Harrison)
Newsgroups: comp.compilers
Subject: Regular expressions & finite automata.
Keywords: lex
Message-ID: <1990Aug15.144231.6909@esegue.segue.boston.ma.us>
Date: 15 Aug 90 14:42:31 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: Mike Harrison <mph@inmos.com>
Organization: Compilers Central
Lines: 30
Approved: compilers@esegue.segue.boston.ma.us

In response to tfd!kent@uunet.UU.NET (Kent Hauser), John wrote:

[Given the well-known equivalence between regular expressions and finite
state machines (albeit not a one-to-one equivalence) there are many programs
that compile regular expressions into FSMs and then run them.  
...]

In my copy of Aho & Ullman - 'The theory of parsing translation and
compiling', regular sets are shown to be equivalent to:
  - regular expressions,
  - right linear grammars,
  - finite automata.

Thus, I don't quite understand the "albeit not a one-to-one
equivalence" above.

Incidentally, this book is an excellent reference for a rigorous treatment of
many aspects of language theory.

Mike,

Michael P. Harrison - Software Group - Inmos Ltd. UK.
UK : mph@inmos.co.uk, US : mph@inmos.com
[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]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.