Chapter 14 The finite state control structure 1 Analogy How are you feeling right now Maybe you are happy or sleepy dopey or grumpy hungry or angry Maybe you feel several of these at once but for simplicity let s assume that just one word describes your current state How did you come to be in this state Clearly your state is affected by things that happen to you the inputs you receive But input alone does not determine how you feel For example receiving a 90 on an exam can leave you either delighted or disappointed depending on your expectations Hence your current state is really a function of two factors your state a little while ago and the input you have received since then In other words your state at time t 1 is determined by your state 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 a combination of previous state and input is the basis for a set of computational models called finite state machines FSMs The FSM models in turn leads us in a very natural way to a powerful and broadly applicable programming strategy which we will examine in this chapter 2 Introduction Computational models or models of computation are abstractions of devices that produce outputs answers from inputs data For simplicity we ll assume a basic model of a computational device as a black box that has a single input channel and a single output channel One simple physical form of a such a computational device would be a black box with a set of buttons on the front exactly one of which can be pressed at any time and a set of lights on the top exactly one of which is lit at any time An input value is specified by pressing one of the buttons the output value is specified by the single light that is lit We can easily think of this device as producing a single output light in response to 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 Weiss Chapter 14 Finite State Machines Page 2 inputs by punching one button after another and producing a sequence of outputs by one light after another being lit The most recent input is often referred to as the current input and the light currently lit is the current output Note that what goes on inside the box can be very complicated or even random this simple model can be modified to accommodate any computational task we like But we are interested only in a small set of the possible behaviors of the box and we are interested only in behaviors that are deterministic The simplest computational model is one in which the box computes a function of the input value Such a box will produce an output value turn on a light solely on the basis of the current input value the last button pressed Because the output value is determined only by the most recent input value we say that the computation requires no memory this means that no information about previous inputs has to be stored to perform the computation 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 information about past inputs in determining its output Conceptually we can imagine a device that keeps track of every input it has processed that is the entire input history Simpler devices might keep track of less information such as how many times the leftmost button was pressed but even this information is unbounded in the sense that the number that must be stored 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 which can store only a finite amount of information and give outputs that depend on that information and the input A Finite State Machine is a device that can be in any one of a specified finite set of states and 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 alternative model for controlling program execution Recall that program control is what determines which program statement or block of statements is to be executed next The most common control structure is the default sequential structure this causes the statements of a program to be executed sequentially one after another just as they appear in the program The other control structures are 1 Alternative selection This is usually embodied as an if if else or switch statement 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 block of 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 a number of times with exit from the loop based on a test 3 Subroutine This causes the current action to be suspended Control then branches to the subroutine code upon completion of the subroutine the original action resumes where it left off Often recursion which occurs when a subroutine calls Printed Chapter 14 Finite State Machines Page 3 itself is treated as a separate control structure but we choose to include it under the subroutine structure To this collection we now add the finite state control structure which chooses a statement to execute or a block of statements or a subroutine to call based on the state of a finite state machine and the most recent input The remainder of this chapter will define finite state machines and work through several simple examples to develop the concept and to give you practice in working with them Then we will give some examples to show how the finite state machine can be used to solve a more complex problem 3 The Basic Finite State Machine Model A finite state machine also called a finite state automaton or simply a finite automaton is a device whose input is a sequence of symbols The automaton is always in some identifiable state Each time an input symbol is received the machine enters a new state although the new state may be the same as the state it was in before At each point the current state of the machine is determined completely by 1 the state it was in prior to the last input and 2 the value of the last input symbol Formally a