State MachinesWhat is a state machine?State machine I/OExample I: Even or oddError statesSimplifying drawings IExample II: Nested parenthesisNested parentheses IINested parentheses IIIThe states of a ThreadGerman vocabulary tutor IGerman vocabulary tutor IIExample: Making numbers boldState machines in JavaOutline of the bold programThe two statesConclusionsThe EndState MachinesWhat 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 knowledgeState 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 inExample 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•Inputs are the characters of a string•The “output” is the resultant stateAeven oddstartAanything but Aanything but AError 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 stateSimplifying 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)•How can we extend this machine to handle arbitrarily deep nesting?start)()()(OKError)* * * *(*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 featuresNested parentheses III•This machine is based on a state machine, but it obviously is not just a state machineOK( do count=1) and count==1do count=0( do count++) and count>1 do count--startThe 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 machinereadywaitingrunning deadstartGerman 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 machineGerman vocabulary tutor II•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 session0th 1st 2nd 3rdrightrightrightrightstartwrongwrongwrongoutExample: Making numbers bold•In HTML, you indicate boldface by surrounding the characters with <b> ... </b>NORMAL NUMBERdigitoutput <b>digitnondigitoutput </b>nondigit*: output *end of inputoutput </b>startdigitoutput digitendState 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 transitionsOutline 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 statescase 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 limitationsThe
View Full Document