Outline for Lecture, Nov 20, 1997 New topic - not covered in book (but in HW7) STATE MAHINES -------------------- Also called finite automata FSM simple machine fixed number of states changes state based on input may output when state changes look at a simple example lets call states s0, s1, ... simple machine may just have inputs 0 and 1 we can describe the machine using a simple table start filling in table 0 1 s0 s1 s2 s1 s0 s2 It may be easier to look at a FSM as a graph. (This is why we do this here in the course) (draw corresponding graph on the board) We can associate an output with entering each state. Lets put 1 for s0 and 0 for everything else (- draw inside circles for states) So what do you do with a FSM? Suppose you want to know if an even number of 1's and an even number of 0's have been input. How would we build a FSM to check for this? Its what we've already started. s0 is the initial state - even number of 0's and even number of 1's what do the other states represent? (ask) s1 is odd 0's, s2 is odd 1's any more states? (ask) s3 is odd both (finish filling in table with help from class) 0 1 even both s0 s1 s2 odd 0's s1 s0 s3 odd 1's s2 s3 s0 odd both s3 s2 s1 The graph can make something like this much more obvious. show that pair of same input always returns to same state. FSM is said to accept a string if it ends in a "1" state. The possible inputs are called the alphabet for the FSM. Machines with outputs associated with states are called "Moore machines" (not tested on names) Alternative is to associate output with edges (called "Mealy"). This is what is more commonly done in hardware and can result in fewer states required. Harder to draw though. Lets look at a common Mealy machine - a coke machine (accepts 10 and 25, returns nickels, dimes and quarters) coke costs 40 cents Lets create a state for each amount of money thats been deposited. Set up first line of table. Ask for ways to fill in. dime quarter s0 s10 s25 s10 s20 s35 s20 s30 s0, output coke, nickel s25 s35 s0, output coke, dime s30 s0, output coke s0, output coke, dime, nickel s35 s0, output coke, nickel s0, output coke, 2 dimes Lets try draw the graph of this as a Moore machine (draw states and start adding edges - point out problem when we get to s20,quarter). need to add states for s40, s45, s50, s55 and s60. only differ in output. Same transition as s0. Now a little trickier example as a Moore machine problem: detect whether a binary number is divisible by three? We are given bits starting with MSB down to LSB. Output 1 whenever number thus far seen is divisble by 3, 0 otherwise. Example 1101 (13) in out 1 0 1 1 0 1 1 0 Claim: this can be done using only 3 states Any ideas? (ask) Idea: 1 state for number so far is divisble by 3 1 state for number so far mod 3 is 1 1 state for number so far mod 3 is 2 draw three states on board, 1 in s0, 0 in s1 and s2 (build 1 table with formulas in it) each digit read doubles previous number and possible adds 1 in state s0, we have some number 3n+0. Doubled is 3(2n)+0 (or +1) in state s1, we have some number 3n+1. Doubled is 3(2n)+2 (or +3) in state s2, we have some number 3n+2. Doubled is 3(2n)+4 (or +5) (table for fsm) 0 1 s0 s0 s1 s1 s2 s0 s2 s1 s2 (If time) One last example. string searching pattern is M chars in a file N chars long. Usually N >> M Simple approach: for (i = 0; i < N; i++) if (strncmp(text+i,pattern,M) == 0) found it running time is N*M Knuth-Morris-Pratt algorithm Idea: Build FSM that says if we have matched the first i chars so far Lets look at an example searching for string aabba a b other . s0 s1 s0 s0 a s1 s2 s0 s0 aa s2 s2 s3 s0 (ASK Why s2 for a input) aab s3 s0 s4 s0 aabb s4 s0 (*1) s0 s0 consider the input a b a a a b b a a a b b a a b b a a gives the output 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0