Two-Way Deterministic Finite Automata
Hing Leung · Mathematical Association of America eBooks · 2009
Introduction 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 [2] wrote the first paper on finite automata, which proved a theorem that we now call Kleene's theorem. 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 on the theory of finite automata, for which they received the Turing award in 1976, the highest award in computer science. The citation for the Turing Award states that the award was granted: For their joint paper “Finite Automata and Their Decision Problem,” which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field. In this project, we will not discuss nondeterministic machines. We consider two-way finite automata which is another concept that was introduced in the seminal paper by Rabin and Scott [5]. In an early stage, the theory of finite automata was developed as a mathematical theory for sequential circuits. A sequential circuit maintains a current state from a finite number of possible states. The circuit logic (which is a finite state control) decides the new state based on the current state of the circuit and the given input symbol.