Regular Languages and Finite Automata
Hing Leung · 2013
In 1943, McCulloch and Pitts [4] published a pioneering work on a model for studying the behavior of the nervous systems. Following up on the ideas of McCulloch and Pitts, Kleene [3] wrote the first paper on finite automata and regular expressions. 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. In a 1959 paper [5], Michael Rabin and Dana Scott presented a comprehensive study of the theory of finite automata, for which they received the Turing Award, the highest award in computer science. In this project, we study from [3] Kleene’s concept of finite automata and regular expressions. In particular, we learn Kleene’s own proof of the theorem (which is now called Kleene’s theorem) that shows finite automata and regular expressions are equivalent in their expressiveness for denoting languages.