Preface
This is a book about solving problems related to automata and regular expressions. There is very little theory here. We cover a few interesting classes of problems for finite state automata and then show some examples of infinite state automata and recursive regular expressions. The final problem in the book involves constructing a recursive regular expression for matching regular expressions.
You will probably get the most out of this book if you already know something about automata and regular expressions. Since you were curious enough to look at the contents of this book, you most likely at least know what they are. The introduction does provide some background information on automata, regular expressions, and generating functions. Out of these three topics the last is the one that most people are probably least familiar with. The generating function associated with an automaton and regular expression will tell you how many strings of a given length are accepted by the automaton.
The inclusion of generating functions is one of the unique features of this book. Few computer science books cover the topic of generating functions for automata and there are only a handful of combinatorics books that mention it. This is unfortunate since we believe the connection between computer science and combinatorics, that is opened up by these generating functions, can enrich both subjects and lead to new methods and applications. The generating functions for infinite state automata are especially interesting and ripe for investigation. The last problem in the book for example, shows how to derive the generating function for the number of syntactically correct regular expressions of a given length.
After the introduction comes a section on using automata to solve divisibility problems. Given a representation for integers in binary, octal, decimal, hexadecimal, etc. it is possible to construct an automaton that will test if an integer is divisible by some other integer. It is also possible to test for divisibility by one integer but not by another and so on.
Next comes a section on pattern matching in strings. This includes general problems on finding strings where runs of some symbols are required or restricted or particular numbers of symbols must occur. There is a description of how to construct automata for efficiently matching a particular pattern in a string. This is essentially the Knuth-Morris-Pratt string searching algorithm, although we do not go into the details of the algorithm and restrict ourselves to constructing automata, regular expressions and generating functions. Problems on three and four bit patterns in binary strings are worked out along with some patterns in ternary and quaternary strings. Some of the more challenging problems in this section are the ones involving patterns in circular strings. These are strings with symbols arranged in circular order with no beginning or end.
The final section is called miscellaneous problems and it contains some of the most challenging problems in the book. Some of the problems are of a more combinatorial nature. There is one related to the coupon collector problem in combinatorics and probability. There are a few problems related to random walks and the gamblers ruin problem. The problems are generalized in a way that provides an easy introduction to the subject of infinite state automata and recursive regular expressions. For example the problem of correctly nested parentheses is first solved in the case where the nesting depth is restricted to 5. We then show how to remove the restriction and how this changes the regular expression into a recursive form and how the generating function can also be solved for recursively. Several infinite forms of the gamblers ruin problem are also solved. The final problem deals with finding a recursive regular expression for matching regular expressions over a binary alphabet. A list of all the syntactically correct regular expressions of length 1, 2, 3, and 4 are given in the solution. The recursive regular expressions in this section are also a nice way of introducing the topic of context free grammars. The context free grammars for some of the recursive regular expressions in these problems are also given.
This book's web page is: http://www.abrazol.com/books/automata/
We can be reached by email at:
stefan[at]exstrom DOT com richard[at]exstrom DOT com
Stefan Hollos and J. Richard Hollos
Exstrom.com
QuantWolf.com
Exstrom Laboratories LLC
Longmont, Colorado, U.S.A.
Aug 2013