Wed, 15 Dec 1993 13:15:31 GMT

Related articles |
---|

Report announcement: Taxonomies of finite automata algorithms watson@win.tue.nl (1993-12-15) |

Newsgroups: | comp.compilers,comp.theory,comp.programming |

From: | watson@win.tue.nl (Bruce W. Watson) |

Keywords: | lex, DFA, report |

Organization: | Eindhoven University of Technology, the Netherlands |

Date: | Wed, 15 Dec 1993 13:15:31 GMT |

I would like to announce the following technical reports (which may be of

interest to the readers of this newsgroup):

``A taxonomy of finite automata construction algorithms,'' by Bruce W.

Watson, Computing Science Note 93/43, Eindhoven University of Technology,

Eindhoven, The Netherlands, 87 pages (including index), 1993.

``A taxonomy of finite automata minimization algorithms,'' by Bruce W.

Watson, Computing Science Note 93/44, Eindhoven University of Technology,

Eindhoven, The Netherlands, 23 pages, 1993.

Below, I've included the abstracts and some information on obtaining copies:

ABSTRACT (construction algorithms):

This paper presents a taxonomy of finite automata construction algorithms.

Each algorithm is classified into one of two families: those based upon

the structure of regular expressions, and those based upon the

automata-theoretic work of Myhill and Nerode.

Many of the algorithms appearing in the literature are based upon the

structure of regular expressions. In this paper, we make this term precise

by defining regular expressions as a $\Sigma$-term algebra, and automata

constructions as various $\Sigma$-algebras of automata. Each construction

algorithm is then presented as the unique natural homomorphism from the

$\Sigma$-term algebra of regular expressions to the appropriate

$\Sigma$-algebra of automata. The concept of duality is introduced and

used to derive more practical construction algorithms. In this way, we

successfully present (and relate) algorithms given by Thompson, Berry and

Sethi, McNaughton and Yamada, Glushkov, and Aho, Sethi, and Ullman.

Efficient implementations (including those due to Chang and Paige, and

Br\"uggemann-Klein) are also treated. As a side-effect we derive several

new algorithms.

A pair of impractical, but theoretically interesting, construction

algorithms were presented by Myhill and Nerode. Some encoding techniques

are used to make the algorithms practical --- giving Brzozowski's

algorithm based upon derivatives. DeRemer's algorithm is derived as an

encoding of Brzozowski's algorithm. Two new algorithms, related to

DeRemer's, are derived. Lastly, this family of algorithms is related to

the first family.

In addition to classifying the algorithms, we identify (and abstract from)

the coding tricks and implementation details present in many of the

published algorithms. This paper also presents an introduction to finite

automata, $\Sigma$-algebras, and their properties.

----

ABSTRACT (minimization algorithms):

This paper presents a taxonomy of finite automata minimization algorithms.

Brzozowski's elegant minimization algorithm differs from all other known

minimization algorithms, and is derived separately. All of the remaining

algorithms depend upon computing an equivalence relation on states. We

define the equivalence relation, the partition that it induces, and its

complement. Additionally, some useful properties are derived. It is shown

that the equivalence relation is the greatest fixed point of an equation,

providing a useful characterization of the required computation. We derive

an upperbound on the number of approximation steps required to compute the

fixed point. Algorithms computing the equivalence relation (or the

partition, or its complement) are derived systematically in the same

framework. The algorithms include Hopcroft's, several algorithms from

text-books (including Hopcroft and Ullman's, Wood's, and Aho, Sethi, and

Ullman's), and several new algorithms or variants of existing algorithms.

----

To obtain copies, email a request to me at watson@win.tue.nl, phone me at

+31 40 474319, or write to me at:

Bruce Watson HG7.39

Fac. W & I

Eindhoven University of Technology

P.O. Box 513

5600 MB Eindhoven

The Netherlands

I'm not making these available for ftp for a number of reasons, two of them

being: I would like to be able to distribute an errata list (if needed) to

people, and I don't have easy access to the local ftp server.

If you do get a copy, please feel free to distribute it to anyone (for

free, of course).

The following five versions are available:

1. PostScript, two pages to one physical page. Saves paper, but can be

tough on the eyesight.

2. PostScript, one page to a physical page (normal).

3. PostScript (600 dpi), one page to a physical page (normal), for use

with high-resolution printers.

4. DVI (for those that don't have PostScript printers, but can print DVI).

5. Paper (discouraged, but if you have no printer or electronic access).

Sincerely,

Bruce.

--

_____________________________________________________________________________

Bruce Watson || favourite oxymoron: "-- rather, it simply

watson@win.tue.nl || complicates our implementation." from

watson@stack.urc.tue.nl || C++ Primer, 2nd ed. (p.501) by S. Lippman

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.