§11.2 – Finite State Machines with Output by Dr. Michael P. Frank, University of Florida Modified by Longin Jan Latecki, Temple University • Remember the general picture of a computer as being a transition function T:S×I→S×O? – If the state set S is finite (not infinite), we call this system a finite state machine. • If the domain S×I is reasonably small, then we can specify T explicitly by writing out its complete graph. – However, this is practical only for machines that have a very small information capacity. Size of FSMs • The information capacity of an FSM is C = log |S|. – Thus, if we represent a machine having an information capacity of C bits as an FSM, then its state transition graph will have |S| = 2C nodes. • E.g. suppose your desktop computer has a 512MB memory, and 60GB hard drive. – Its information capacity, including the hard drive and memory (and ignoring the CPU’s internal state), is then roughly ~512×223 + 60×233 = 519,691,042,816 b. – How many states would be needed to write out the machine’s entire transition function graph? 2519,691,042,816 = A number having >1.7 trillion decimal digits! One Problem with FSMs as Models • The FSM diagram of a reasonably-sized computer is more than astronomically huge. – Yet, we are able to design and build these computers using only a modest amount of industrial resources. • Why is this possible? • Answer: A real computer has regularities in its transition function that are not captured if we just write out its FSM transition function explicitly. – I.e., a transition function can have a small, simple, regular description, even if its domain is enormous. Other Problems with FSM Model • It ignores many important physical realities: – How is the transition function’s structure to be encoded in physical hardware? • How much hardware complexity is required to do this? – How close in physical space is one bit’s worth of the machine’s information capacity to another? • How long does it take to communicate information from one part of the machine to another? – How much energy gets dissipated to heat when the machine updates its state? • How fast can the heat be removed, and how much does this impact the machine’s performance? Vending Machine Example • Suppose a certain vending machine accepts nickels, dimes, and quarters. – If >30¢ is deposited, change is immediately returned. • If the “coke” button is pressed, the machine drops a coke. – It can then accept a new payment. Ignore any other buttons, bills, out of change, etc. Modeling the Machine • Input symbol set: I = {nickel, dime, quarter, button} – We could add “nothing” or as an additional input symbol if we want. • Representing “no input at a given time.” • Output symbol set: O = {, 5¢, 10¢, 15¢, 20¢, 25¢, coke}. • State set: S = {0, 5, 10, 15, 20, 25, 30}. – Representing how much money has been taken. Transition Function Table Old state Input New state Output Old state Input New state Output 0 n 5 10 n 15 0 d 10 10 d 20 0 q 25 10 q 30 5¢ 0 b 0 10 b 10 5 n 10 15 n 20 5 d 15 15 d 25 5 q 30 15 q 30 10¢ 5 b 5 15 b 5 Transition Function Table cont. Old state Input New state Output Old state Input New state Output 20 n 25 30 n 30 5¢ 20 d 30 30 d 30 10¢ 20 q 30 15¢ 30 q 30 25¢ 20 b 20 30 b 25 n 30 25 d 30 5¢ 25 q 30 20¢ 25 b 25 0 coke Another Format: State Table Old state Input Symbol n d q b 0 5, 10, 25, 0, 5 10, 15, 30, 5, 10 15, 20, 30,5¢ 10, 15 20, 25, 30,10¢ 15, 20 25, 30, 30,15¢ 20, 25 30, 30,5¢ 30,20¢ 25, 30,10¢ 30,25¢ 0,coke 30 30,5¢ Each pair shows new state, output symbol Directed-Graph State Diagram • As you can see, these can get kind of busy. q,5¢ q 0 b nd 5 b n 10 b d n d,5¢ q 15 n b b,coke d q,20¢ 20 n 25 n 30 b b q,15¢ q,10¢ n,5¢ d,10¢ q,25¢ Formalizing FSMs • Just like the general transition-function definition from earlier, but with the output function separated from the transition function, and with the various sets added in, along with an initial state. • A finite-state machine M=(S, I, O, f, g, s0) – – – – – – S is the state set. I is the alphabet (vocabulary) of input symbols O is the alphabet (vocabulary) of output symbols f is the state transition function g is the output function s0 is the initial state. • Our transition function from before is T = (f,g). Construct a state table for the finite-state machine in Fig. 3. Find the output string for the input 101011 A unit-delay machine: Construct a finite-state machine that delays an input string by one unit of time: Input: x1x2 … xk-1xk Output: 0x1x2 … xk-1 Language recognizer: Construct a finite-state machine that outputs 1 iff the input string read so far ends with 111.

Descargar
# Slides for Rosen, 5th edition