Regular expressions & finite automata.

Mike Harrison <mph@inmos.com>
Wed, 15 Aug 90 14:42:31 GMT

          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: Mike Harrison <mph@inmos.com>
Keywords: lex
Organization: Compilers Central
Date: Wed, 15 Aug 90 14:42:31 GMT

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


Post a followup to this message

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