Modeling Arithmetic, Computation, and LanguagesFinite-State MachinesSlide 3Example: Finite-State MachineState GraphRecognizersRegular SetsSlide 8Examples: Regular ExpressionsKleene’s TheoremUnreachable StatesExample: Unreachable StatesEquivalent StatesMinimizationExample: k-Equivalent StatesSlide 16Minimization AlgorithmSlide 18ExampleSlide 20Sequential NetworkModeling Arithmetic, Computation, and LanguagesMathematical Structures for Computer ScienceChapter 8Copyright © 2006 W.H. Freeman & Co. MSCS Slides Finite State MachinesSection 8.2 Finite State Machines 2Finite-State MachinesThe finite-state machine is a model that captures the characteristics of a computer. The behavior of our abstract machine is exhibited by the following properties:Operations of the machine are synchronized by discrete clock pulses. The machine proceeds in a deterministic fashion; that is, its actions in response to a given sequence of inputs are completely predictable. The machine responds to inputs. The machine can attain a finite number of states. •At any given moment, the machine is in exactly one of these states. •Which state it will be in next is a function of both the present state and the present input.The machine is capable of output. •The nature of the output is a function of the present state of the machine, meaning that it also depends on past inputs.Section 8.2 Finite State Machines 3Finite-State MachinesDEFINITION: FINITE-STATE MACHINE M[S, I, O, fS, fO] is a finite-state machine if S is a finite set of states, I is a finite set of input symbols (the input alphabet), O is a finite set of output symbols (the output alphabet), and fS and fO are functions where fS: S  I  S and fO: S  O. The machine is always initialized to begin in a fixed starting state s0.The function fS is the next-state function. It maps a (state, input) pair to a state. Thus, the state at clock pulse ti + 1, state(ti + 1),is obtained by applying the next-state function to the state at time ti and the input at time ti : state(ti + 1) = fS(state(ti ), input(ti )) The function fO is the output function. When fO is applied to a state at time ti , we get the output at time ti : output(ti ) = fO(state(ti ))Section 8.2 Finite State Machines 4Example: Finite-State MachineA finite-state machine M is described as follows: S = {s0, s1, s2}, I = {0,1}, O = {0,1}. Because the two functions fS and fO act on finite domains, they can be defined by a state table, as in Table 8.1. The machine M begins in state s0, which has an output of 0. If the first input symbol is a 0, the next state of the machine is then s1, which has an output of 1.Section 8.2 Finite State Machines 5State GraphAnother way to define the functions fS and fO (in fact all of M) is by a directed graph called a state graph. Each state of M with its corresponding output is the label of a node of the graph.The next-state function is given by directed arcs of the graph, each arc showing the input symbol(s) that produces that particular state change. The state graph for M appears in the figure below:Section 8.2 Finite State Machines 6RecognizersFinite machines can be used as recognizers because of the (limited) memory of past inputs represented by the states of a machine.A machine can be built to recognize, say by producing an output of 1, when the input it has received matches a certain description. To avoid writing down outputs, we shall designate those states of a finite-state machine with an output of 1 as final states and denote them in the state graph with a double circle. The following is the formal definition of recognition, where I* denotes the set of finite-length strings over the input alphabet.DEFINITION: FINITE-STATE MACHINE RECOGNITION A finite-state machine M with input alphabet I recognizes a subset S of I* if M, beginning in state s0 and processing an input string, ends in a final state if and only if   S.Section 8.2 Finite State Machines 7Regular SetsDEFINITION: REGULAR EXPRESSIONS OVER I Regular expressions over I are the symbol  and the symbol . the symbol i for any i  I. the expressions (AB), (A  B), and (A)* if A and B are regular expressions. (This definition of a regular expression over I is still another example of a recursive definition.)Section 8.2 Finite State Machines 8Regular SetsDEFINITION: REGULAR SET Any set represented by a regular expression according to the following conventions is a regular set:  represents the empty set.  represents the set {} containing the empty string.i represents the set {i}. For regular expressions A and B, •(AB) represents the set of all elements of the form , where  belongs to the set represented by A and  belongs to the set represented by B. •(A  B) represents the union of A’s set and B’s set.•(A)* represents the set of all concatenations of members of A’s set.Section 8.2 Finite State Machines 9Examples: Regular ExpressionsHere are some regular expressions and a description of the set each one represents. 1*0(01)* •Any number (including none) of 1s, followed by a single 0, followed by any number (including none) of 01 pairs0  1* •A single 0 or any number (including none) of 1s(0  1)* •Any string of 0s or 1s, including 11((10)*11)*(00*) •A nonempty string of pairs of 1s interspersed with any number (including none) of 10 pairs, followed by at least one 0Section 8.2 Finite State Machines 10Kleene’s TheoremKLEENE’S THEOREM Any set recognized by a finite-state machine is regular, and any regular set can be recognized by some finite-state machine.Minimization is the process of finding, for a given finite-state machine M, a machine M with two properties: If M and M are both begun in their respective start states and are given the same sequence of input symbols, they will produce identical output sequences. M has, if possible, fewer states than M. •If this is not possible, then M is already a minimal machine and cannot be further reduced.Section 8.2 Finite State Machines 11Unreachable StatesUnreachable states of M are those states that cannot be attained from the starting state no matter what input sequence occurs.Any of these unreachable states can be removed.Let M be given by the state table of Table 8.3.Section 8.2 Finite State Machines 12Example: Unreachable StatesAlthough the state