|
|
|
|
|
|
 |
 |
|
Algorithms on Finite Automata, parts I - IV
|
|
|
|
|
|
| Organization: | Universidad Autonoma de Querétaro |
| Department: | Facultad de Informatica |
|
|
|
|
|
|
0210-249
|
|
|
|
|
|
1999-06-30
|
|
|
|
|
|
 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.
|
|
|
|
|
|
|
|
|
|
|
|
finite automata, states, minimization, boolean operations, words, enumeration, Automata, Regular expressions, Nondeterminism, Arden's lemma, Reverse Automata, Regular Language, Counting, enumerating, fractal
|
|
|
 |
|
|
| 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 |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
