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 ThreadExample: Making numbers boldState machines in JavaOutline of the bold programThe two statesConclusionsThe EndJan 13, 2019State Machines2What is a state machine?A state machine is a different way of thinking about computationA state machine has some number of states, and transitions between those statesTransitions occur because of inputsA “pure” state machine only knows which state it is in—it has no other memory or knowledgeThis is the kind of state machine you learn about in your math classesWhen you program a state machine, you don’t have that restriction3State machine I/OState machines are designed to respond to a sequence of inputs, such asThe individual characters in a stringA series of external eventsState machines may produce output (often as a result of transitions)Alternatively, the only “result” of a state machine may be the state it ends up in4Example I: Even or oddThe following machine determines whether the number of As in a string is even or oddCircles represent states; arrows represent transitionsInputs are the characters of a stringThe “output” is the resultant stateThe double circle represents a “final” (accepting) stateAeven oddstartAanything but A anything but A5Error statesAgain, a state machine is a way of doing certain kinds of computationsThe input is a sequence of values (typically, a String)Some inputs may be illegal (for example, syntax errors in a program)A state machine is used to recognize certain kinds of inputsWe say the machine succeeds if it recognizes its input, otherwise it failsSome states may be marked as final states (they are drawn with concentric circles)A state machine succeeds if:It is in a final state when it reaches the end of its inputA state machine fails if:It encounters an input for which it has no defined transitionIt reaches the end of its input, but is not in a final stateState machines may have a error state with the following characteristics:The error state is not a final stateAn unexpected input will cause a transition to the error stateAll subsequent inputs cause the state machine to remain in the error state6Simplifying drawings IState machines can get pretty complicatedThe formal, mathematical definition of a state machine requires it to have a transition from every state for every possible inputTo satisfy this requirement, we often need an error state, so we can have transitions for illegal (unrecognized) inputsWhen we draw a state machine, we don’t need to draw the error state--we can just assume it’s thereThe error state is still part of the machineAny input without a transition on our drawing is assumed to go to the error stateAnother 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 input7Example II: Nested parenthesisThe 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)* * * *(*8Nested parentheses IIQuestion: 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 inHowever, if we aren’t required to use a pure state machine, we can add memory (such as a counter) and other features9Nested parentheses IIIThis 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--start10The states of a ThreadA Thread is an object that represents a single flow of execution through a programA Thread’s lifetime can be described by a state machinereadywaitingrunning deadstart11Example: Making numbers boldIn 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 thisNORMAL NUMBERdigitoutput <b>digitnondigitoutput </b>nondigit*: output *end of inputoutput </b>startdigitoutput digitend12State machines in JavaIn a state machine, you can have transitions from any state to any other stateThis is difficult to implement with Java’s loops and if statementsThe trick is to make the “state” a variable, and to embed a switch (state) statement inside a loopEach case is responsible for resetting the “state” variable as needed to represent transitions13Outline 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>");14The 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;15ConclusionsA state machine is a good model for a number of problemsYou can think of the problem in terms of a state machine but not actually do it that wayYou can implement the problem as a state machine (e.g. making integers bold) Best done as a switch inside some kind of loopPure state machines have some severe limitationsJava lets you do all kinds of additional tests and actions; you can ignore these limitations16The
View Full Document
Unlocking...