DOC PREVIEW
Penn CIT 591 - State Machines

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 ThreadA Memorization programItem statesExample: 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 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 restriction3State 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 in4Example 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 A5Error 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 state6Simplifying 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 input7Example 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)* * * *(*8Nested 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 features9Nested 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--start10The 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 deadstart11A 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 program12Item states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. 0th 1st 2nd 3rdrightrightrightrightstartwrongwrongwrongout13Example: 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 thisNORMAL NUMBERdigitoutput <b>digitnondigitoutput </b>nondigit*: output *end of inputoutput </b>startdigitoutput digitend14State 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 transitions15Outline 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>");16The 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;17Conclusions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 limitations18The


View Full Document

Penn CIT 591 - State Machines

Documents in this Course
Stacks

Stacks

11 pages

Arrays

Arrays

30 pages

Arrays

Arrays

29 pages

Applets

Applets

24 pages

Style

Style

33 pages

JUnit

JUnit

23 pages

Java

Java

32 pages

Access

Access

18 pages

Methods

Methods

29 pages

Arrays

Arrays

32 pages

Methods

Methods

9 pages

Methods

Methods

29 pages

Vectors

Vectors

14 pages

Eclipse

Eclipse

23 pages

Vectors

Vectors

14 pages

Recursion

Recursion

24 pages

Animation

Animation

18 pages

Animation

Animation

18 pages

Static

Static

12 pages

Eclipse

Eclipse

23 pages

JAVA

JAVA

24 pages

Arrays

Arrays

29 pages

Animation

Animation

18 pages

Numbers

Numbers

21 pages

JUnit

JUnit

23 pages

Access

Access

18 pages

Applets

Applets

24 pages

Methods

Methods

30 pages

Buttons

Buttons

20 pages

Java

Java

31 pages

Style

Style

28 pages

Style

Style

28 pages

Load more
Download State Machines
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view State Machines and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view State Machines 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?