State Machines 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 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 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 even odd start A anything but anything but A A Inputs are the characters of a string The output is the resultant state 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 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 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 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 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 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 German vocabulary tutor I I once wrote a program to provide memorization drill on English German vocabulary Words were presented in English The user had to type in the German translation A word was considered learned when the user answered correctly three times in a row Each word pair could be thought of as a state machine German vocabulary tutor II wrong wrong start 0th right 1st right wrong 2nd right 3rd right What s the value in thinking of this as a state machine Answer By measuring the percentage correct from each state I was better able to adjust the difficulty of the study session out Example Making numbers bold In HTML you indicate boldface by surrounding the characters with b b end of input output b digit output b digit start NORMAL output NUMBER nondigit output b nondigit end digit output digit 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 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 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 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 The End
View Full Document
Unlocking...