In this project for computer science students in a theory of computation course, we study Kleene’s concept of finite automata and regular expressions. While a lower level assembly-styled language with simpler syntax is sufficient to program the computer to do whatever a high level language can do, the programming community embraces higher level programming languages like Java, C++, and Python for higher productivity. A similar situation happens with programming languages. However, Kleene’s more complex model of finite automata actually allows the user to express ideas more easily, even though formally both models are equivalent in their expressiveness. In a paper published in 1959, Michael Rabin and Dana Scott presented finite automata in the simplest mathematical model. A finite automaton can be considered as the simplest machine model in that the machine has a finite memory that is, the memory size is independent of the input length.

Following on their ideas, Stephen Cole Kleene (1909–1994) wrote the first paper on finite automata and regular expressions in 1956. In 1943, Warren McCulloch and Walter Pitts published a pioneering work on a logical model for studying the behavior of nervous systems in the Bulletin of Mathematical Biophysics. Stephen Cole Kleene (Source: Wikimedia Commons)

Math finite state automata