An algorithmic approach to constructing finite automata

Abstract

In this thesis, we introduce algorithms for creating deterministic (DFA) and nondeterministic finite automata (NFA) for some common types of regular languages. The motivation for this work comes from studying problems students taking theory of com-putation classes encounter. When working with finite automata, there are patterns in the structures of automata that arise. This thesis seeks to generalize a subset of common problems by creating step-by-step constructions based on the distinguishing properties of the given language. Along with these algorithms, software has been developed to generate these automata based on their dis-tinguishing properties. This thesis aims to be the foundation for developing an educational tool for theory of computation students. The goal is to highlight the similarities and logic behind these common constructions, while also providing the visual aid of the constructed automata through the accompanying software. The problems we consider are: the Maximum Prefix-Suffix Overlap problem, the Substring problems, the X followed by Y problem, the Consecutive Character problems, the Conditional Counting Modulo n problems, the Regularly Repeated Characters problem, and the Contains X but not Y problem. All algorithms presented in this thesis are polynomial in runtime, and polynomial in space complexity. The Maximum-Prefix-Suffix Overlap problem has a linear runtime, and the Contains X but not Y problem is of special interest due to its space reduction from the ‘usual’ solution.