1 Analogy2 Introduction3 The Basic Finite State Machine Model3.1 Example: the stamp machine4 Implementing a FSM5 Final output machines6 Acceptor machines7 String Searching7.1 Naive String Search (Algorithm A)7.2 Finite State String Search (Algorithm B)8 What a FSM cannot do9 Extensions to the basic model9.1 Integer Reader 19.2 Integer Reader 29.3 Comment locator9.4 Text Compression10 Summary11 ExercisesChapter 14The finite state control structure1 AnalogyHow are you feeling right now? Maybe you are happy or sleepy, dopey or grumpy, hungryor angry. Maybe you feel several of these at once, but for simplicity, let’s assume that justone word describes your current state. How did you come to be in this state? Clearly yourstate is affected by things that happen to you — the inputs you receive. But input alonedoes not determine how you feel. For example, receiving a 90% on an exam can leave youeither delighted or disappointed, depending on your expectations. Hence, your currentstate is really a function of two factors: your state a little while ago, and the input youhave received since then. In other words, your state at time t+1 is determined by yourstate at time t and the input you encountered between t and t+1.The notion of state and of transition from one state to another as determined by acombination of previous state and input is the basis for a set of computational modelscalled finite state machines (FSMs). The FSM models in turn leads us in a very naturalway to a powerful and broadly applicable programming strategy which we will examine inthis chapter.2 IntroductionComputational models, or models of computation, are abstractions of devices thatproduce outputs (answers) from inputs (data). For simplicity, we'll assume a basic modelof a computational device as a black box that has a single input channel and a singleoutput channel. One simple physical form of a such a computational device would be ablack box with a set of buttons on the front, exactly one of which can be pressed at anytime, and a set of lights on the top, exactly one of which is lit at any time. An input value isspecified by pressing one of the buttons; the output value is specified by the single lightthat is lit. We can easily think of this device as producing a single output (light) in responseto a single input (button). But we can also think of the device as being given a sequence of© 2001 Donald F. Stanat and Stephen F. WeissChapter 14 Finite State Machines Page 2inputs (by punching one button after another) and producing a sequence of outputs (byone light after another being lit). The most recent input is often referred to as the currentinput, and the light currently lit is the current output. Note that what goes on inside thebox can be very complicated or even random; this simple model can be modified toaccommodate any computational task we like. But we are interested only in a small set ofthe possible behaviors of the box, and we are interested only in behaviors that aredeterministic.The simplest computational model is one in which the box computes a function of theinput value. Such a box will produce an output value (turn on a light) solely on the basisof the current input value (the last button pressed). Because the output value is determinedonly by the most recent input value, we say that the computation requires no memory; thismeans that no information about previous inputs has to be stored to perform thecomputation that determines which light shall be lit. Furthermore, given a particular input,say the ith button, the output is always the same.We are interested in a more complex computational model that uses some informationabout past inputs in determining its output. Conceptually, we can imagine a device thatkeeps track of every input it has processed, that is, the entire input history. Simpler devicesmight keep track of less information, such as how many times the leftmost button waspressed, but even this information is unbounded in the sense that the number that must bestored may become arbitrarily large, and require arbitrarily much storage to represent it.We're interested in a simpler class of machines called Finite State Machines (FSM), whichcan store only a finite amount of information, and give outputs that depend on thatinformation and the input. A Finite State Machine is a device that can be in any one of a specified finite set of statesand which can change state as a result of an input. Thus, each time an FSM gets an input,we consider it to change states, although it may enter the same state it was in before. Finite state machines are useful for programming because they provide an alternativemodel for controlling program execution. Recall that program control is what determineswhich program statement (or block of statements) is to be executed next. The mostcommon control structure is the default sequential structure; this causes the statements ofa program to be executed sequentially, one after another, just as they appear in theprogram. The other control structures are1. Alternative selection. This is usually embodied as an if, if...else, or switchstatement. This performs one or more tests, and based on the result of the tests,chooses one block of code from a collection of blocks and executes it. The blockof code may of course be empty, as it is in the false branch of the if statement.2. Iteration. This is any loop structure; it causes some loop body to be executed anumber of times with exit from the loop based on a test.3. Subroutine. This causes the current action to be suspended. Control then branchesto the subroutine code; upon completion of the subroutine, the original actionresumes where it left off. Often recursion (which occurs when a subroutine callsPrinted % , " :Chapter 14 Finite State Machines Page 3itself) is treated as a separate control structure, but we choose to include it underthe subroutine structure.To this collection we now add the finite state control structure, which chooses a statementto execute (or a block of statements or a subroutine to call) based on the state of a finitestate machine and the most recent input. The remainder of this chapter will define finite state machines and work through severalsimple examples to develop the concept and to give you