Finite Automata and Other Models of Computation
Jean‐Paul Allouche, Jeffrey O. Shallit · Cambridge University Press eBooks · 2003
In this chapter, we introduce some simple models of computation, focusing particularly on finite automata and their variants. Finite Automata A deterministic finite automaton , or DFA, is one of the simplest possible models of computation. It is an acceptor ; that is, strings are given as input and are either accepted or rejected. A DFA starts in an initial state and after reading the input can be in one of a finite number of states. The DFA takes as input a string w and — based on the symbols of w , read in order from left to right — moves from state to state. If after reading all the symbols of w the DFA is in a distinguished state called an accepting state (or final state ), then the string is accepted; otherwise, it is rejected. The language accepted by the DFA is the set of all accepted strings. A DFA can be represented by a directed graph called a transition diagram . A directed edge labeled with a letter indicates the new state of the machine if the given letter is read. By convention, the initial state is drawn with an unlabeled arrow entering the state, and accepting states are drawn with double circles.