Finite-State Automata State Transition Table Deterministic FSA Non-deterministic FSA Pushdown Automata Turing Machine

Automata theory is the branch of computer science that is concerned with the study of abstract machines and automata. These include finite-state machines, pushdown automata, and Turing machines. Finite-state machines are abstract machines that may be in one of a finite number of states. These machines are in only one state at a time (current state), and the input symbol causes a transition from the current state to the next state. Finite-state machines have limited computational power due to memory and state constraints, but they have been applied to a number of fields including communication protocols, neurological systems, and linguistics. Pushdown automata have greater computational power than finite-state machines, and they contain extra memory in the form of a stack from which sym- bols may be pushed or popped. The state transition is determined from the current state of the machine, the input symbol, and the element on the top of the stack. The action may be to change the state and/or push/pop an element from the stack.

The Turing machine is the most powerful model for computation, and this theo- retical machine is equivalent to an actual computer in the sense that it can compute exactly the same set of functions. The memory of the Turing machine is a tape that consists of a potentially infinite number of one-dimensional cells. It provides a mathematical abstraction of computer execution and storage, as well as providing a mathematical definition of an algorithm. However, Turing machines are not suit- able for programming, and therefore they do not provide a good basis for studying programming and programming language