Finite Automata and Regular Expressions: Problems and Solutions

This is a book about solving problems related to automata and regular
expressions. It helps you learn the subject in the most effective way
possible, through problem solving. There are 84 problems with
solutions.

The introduction provides some background information on automata,
regular expressions, and generating functions.

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.

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.

This book explains:
* Why automata are important.
* The relationship of automata to regular expressions.
* The difference between deterministic and nondeterministic automata.
* How to get the regular expression from an automaton.
* Why two seemingly different regular expressions can belong to the same
automaton.
* How the regular expression for an infinite automaton is different than
one for a finite one.
* The relationship of a regular expression to a regular language.
* What a generating function for a language tells you about the language.
* How to get a generating function from a regular expression.
* How the generating function of a recursive regular expression is
different from that of an ordinary regular expression.
* How to test divisibility properties of integers (binary and decimal
based) using automata.
* How to construct an automaton to search for a given pattern, or for a
given pattern not occurring.
* How to construct an automaton for arbitrary patterns and alphabets.
* How the recursive regular expression for nested parentheses leads to
the Catalan numbers.

Included in this book:
* Divisibility problems in binary and decimal.
* Pattern search problems in binary, ternary, and quaternary alphabets.
* Pattern search problems for circular strings that contain or do not
contain a given pattern.
* Automata, regular expressions, and generating functions for gambling games.
* Automata and generating functions for finite and infinite correctly
nested parentheses.
* The recursive regular expression for matching regular expressions
over a binary alphabet.
* A further reading list.