Wed, 15 Aug 90 14:42:31 GMT

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

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.