State Machines Jan 13 2019 What is a state machine A state machine is a different way of thinking about computation A state machine has some number of states and transitions between those states Transitions occur because of inputs A pure state machine only knows which state it is in it has no other memory or knowledge This is the kind of state machine you learn about in your math classes When you program a state machine you don t have that restriction 2 State machine I O State machines are designed to respond to a sequence of inputs such as The individual characters in a string A series of external events State machines may produce output often as a result of transitions Alternatively the result of a state machine may be the state it ends up in 3 Example I Even or odd The following machine determines whether the number of As in a string is even or odd Circles represent states arrows represent transitions A start even A anything but A odd anything but A Inputs are the characters of a string The output is the resultant state 4 Error states Some state machines may have a error state with the following characteristics An unexpected input will cause a transition to the error state All subsequent inputs cause the state machine to remain in the error state 5 Simplifying drawings I State machines can get pretty complicated We can simplify the drawing by leaving out the error state The error state is still part of the machine Any input without a transition on our drawing is assumed to go to the error state Another simplification Use to indicate all other characters This is a convention when drawing the machine it does not mean we look for an asterisk in the input 6 Example II Nested parenthesis The following example tests whether parentheses are properly nested up to 3 deep start OK Error How can we extend this machine to handle arbitrarily deep nesting 7 Nested parentheses II Question How can we use a state machine to check parenthesis nesting to any depth Answer We can t with a finite number of states We need to count how deep we are into a parenthesis nest 1 2 3 821 The only memory a state machine has is which state it is in However if we aren t required to use a pure state machine we can add memory such as a counter and other features 8 Nested parentheses III start do count 1 do count and count 1 do count 0 and count 1 do count OK This machine is based on a state machine but it obviously is not just a state machine 9 The states of a Thread A Thread is an object that represents a single flow of execution through a program A Thread s lifetime can be described by a state machine waiting start ready running dead 10 A Memorization program A program to help people memorize paired associates might be designed like this Some stimulus is presented The user has to type in a response A paired associate is considered learned when the user answers correctly three times in a row Each item stimulus response can be thought of as a state machine Here however we are looking at states of data rather than states of a program 11 Item states wrong wrong start 0th right 1st right wrong 2nd right 3rd right out What s the value in thinking of this as a state machine Answer When I wrote one of these for real use I was able to adjust the difficulty of the study session by measuring the percentage correct from each state 12 Example Making numbers bold In HTML you indicate boldface by surrounding the characters with b b Suppose we want to make all the integers bold in an HTML page we can write a state machine to do this end of input output b digit output b digit start NORMAL output NUMBER nondigit output b nondigit end digit output digit 13 State machines in Java In a state machine you can have transitions from any state to any other state This is difficult to implement with Java s loops and if statements The trick is to make the state a variable and to embed a switch state statement inside a loop Each case is responsible for resetting the state variable as needed to represent transitions 14 Outline of the bold program void run int state NORMAL for int i 0 i testString length i char ch testString charAt i switch state case NORMAL not inside a number case NUMBER inside a number if state NUMBER result append b 15 The two states case NORMAL if Character isDigit ch result append b ch state NUMBER break else result append ch break case NUMBER if Character isDigit ch result append b ch state NORMAL break else result append ch break 16 Conclusions A state machine is a good model for a number of problems You can think of the problem in terms of a state machine but not actually do it that way e g German vocabulary You can implement the problem as a state machine e g making integers bold Best done as a switch inside some kind of loop Pure state machines have some severe limitations Java lets you do all kinds of additional tests and actions you can ignore these limitations 17 The End 18
View Full Document
Unlocking...