Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Algorithms on Finite Automata, parts I - IV

Jaime Rangel-Mondragón
Organization: Universidad Autonoma de Querétaro
Department: Facultad de Informatica
Old MathSource #

Revision date


Finite Automata This is a four-part work on implementing finite automata (FA) algorithms.

Part I, "Generating and Enumerating Words", deals with the generation of the set of words accepted by a given FA along with an algebraic formula describing it. Functions for displaying the associated graph of a FA are also provided.

Part II, "Minimization and Boolean Operations", deals with FA minimization and Boolean operations: serial and parallel connection, intersection, complement, difference and Kleene's star. Tree automata is also covered: prefix and set-accepting automata. Suffix and frame FA are also included. Multiple examples are given throughout.

In part III the mutual conversions between deterministic and non-deterministic automata are introduced. Reverse FA serves as an application of these conversions. A brief comment on the implementation of boolean functions via NFA is made. Finally, the conversions among an FA and its language are developed via solving a system of regular expressions and conversely, through building a suitable parser of regular expressions.

Part IV is dedicated firstly to count equivalent FA, i.e., those recognizing infinite languages and which are minimal and not including complements. The last section deals with fractals derived from automata: to every word recognized by a given FA, we associate a quadtree specifying a fractal.

All four parts forming the whole work include an extended variety of examples covering analytical and graphical applications. The work is concisely commented and a bibliography is provided with the purpose of helping to adapt the functions in the four notebooks (which are introduced in an increasing order of dependency) with the theory taught in popular textbooks on the subject.

*Mathematics > Discrete Mathematics > Cellular Automata

finite automata, states, minimization, boolean operations, words, enumeration, Automata, Regular expressions, Nondeterminism, Arden's lemma, Reverse Automata, Regular Language, Counting, enumerating, fractal
Downloads Download Wolfram CDF Player

algorithmsOnAutomata_1.nb (841.8 KB) - Mathematica notebook
algorithmsOnAutomata_2.nb (1.3 MB) - Mathematica notebook
algorithmsOnAutomata_3.nb (337.8 KB) - Mathematica notebook
algorithmsOnAutomata_4.nb (4.6 MB) - Mathematica notebook