Lecture 3: States and EventsExample: States and EventsSlide 3Finite State AutomataStates and EventsFinite State Automata (FSA)FSA Example: A Light SwitchSlide 8FSA: GhostFSA Example: GhostTraffic Lights: SystemTraffic Lights: AnalysisTraffic Lights: StatesTraffic Lights: InputsTraffic Lights: FSATraffic Lights: Tabular FSASlide 17Implementation: PythonSlide 19ExerciseMarkov ModelsNondeterministic AutomataMarkov Example: Diabetes PatientsSlide 24Markov Model ImplementationImplementation: C++Slide 27Slide 28Utilizing the SimulationSlide 30Slide 31Slide 32Production ModelsSlide 34Slide 35Example: Water Jug PuzzleJug Problem: FSA SolutionProduction Rule 1Production Rule 2Production Rule 3Production Rule 4Water Jug System: FSAWater Jug System: SolutionSOURCESCOMP155Computer SimulationSeptember 3, 2008Example: States and EventsExample: States and EventsEvent Driven TransitionsStates and EventsA state is a condition of a system at some point in timeAn event is something that cause a system to shift from one state to anotherFinite State Automata (FSA)a set of states one designated start stateinput alphabetthese are eventsa transition function that maps input symbols and current states to a next stateFSA Example: A Light SwitchONOFFtoggletoggleFSA Example: A Light Switchstates = { ON, OFF }start state = OFFalphabet = { toggle }transition function:current state ON OFFtoggle OFF ONFSA: GhostCHASEROAMsee=falseEVADEblue=truesee=truesee=falsesee=falsesee=trueblue=trueblue=truesee=trueFSA Example: Ghoststates = { ROAM, CHASE, EVADE }start state = ROAMalphabet = { see=true, see=false, blue=true }transition function:current state ROAM CHASE EVADEsee=true CHASE CHASE CHASEsee=false ROAM ROAM ROAMblue=true EVADE EVADE EVADETraffic Lights: Systemsensorslightsinputs:4 sensors clock (every 5 seconds)output:4 lights: red, yellow, greenTraffic Lights: AnalysisEast-West lights are the sameNorth-South lights are the sameClock is used to introduce delayslights do not immediately switch when a vehicle is sensedcaution (yellow) for 10 seconds before stop (red)Traffic Lights: StatesState is made up of three values:NS: color of north and south lightsEW: color of east and west lightsD: integer used to distinguish between delay statesNS: GEW: RD: 0Traffic Lights: InputsInput Alphabet:SNS: north-bound or south-bound sensor triggeredSEW: east-bound or west-bound sensor triggeredC: clock elapsedTraffic Lights: FSANS: GEW: RD: 0NS: GEW: RD: 1NS: YEW: RD: 2NS: YEW: RD: 1NS: REW: GD: 0NS: REW: GD: 1NS: REW: YD: 2NS: REW: YD: 1C CCCCCSEWSNSTraffic Lights: Tabular FSAGR0 GR1 YR2 YR1 RG0 RG1 RY2 RY1C GR0 YR2 YR1 RG0 RG0 RY2 RY1 GR0SNSGR0 GR1 YR2 YR1 RG1 RG1 RY2 RY1SEWGR1 GR1 YR2 YR1 RG0 RG1 RY2 RY1Once the FSA is in tabular form, implementation is straightforward:• hardcode: nested switch statements• flexible: read FSA from a table data structureTraffic Lights: Tabular FSAGR00GR11YR22YR13RG04RG15RY26RY171 = C 0 2 3 4 4 6 7 02 = SNS0 1 2 3 5 5 6 73 = SEW1 1 2 3 4 5 6 7States and inputs mapped to integer codes,to enable table lookupImplementation: Pythonclass TrafficLights: def __init__(self): self.state = 0 self.transitions = ((0,2,3,4,4,6,7,0), (0,1,2,3,5,5,6,7), (1,1,2,3,4,5,6,7)) self.NS_output = ('green', 'green', 'yellow', 'yellow', 'red', 'red', 'red', 'red') self.EW_output = ('red', 'red', 'red', 'red', 'green', 'green', 'yellow', 'yellow') def update(self, input): if (input < 1) or (input > 3): return self.state = self.transitions[input-1][self.state] def display(self): print print 'NS lights: ' + self.NS_output[self.state] print 'EW lights: ' + self.EW_output[self.state] printImplementation: Pythonlights = TrafficLights()while True: lights.display() input = int(raw_input("next input: ")) if input == 0: break lights.update(input)ExerciseDesign a FSA for a soda vending machineProbabilistic TransitionsNondeterministic AutomataA nondeterministic automata has probabilistic transitionscalled Markov modelsImplemented using time-steppingat each clock, probabilities are used to determine next stateMarkov Example: Diabetes PatientsThree states:CD: controlled diabetesESRD: end-stage renal diseaseD: deathTransitions:Each year, patients with controlled diabetes have an 85% chance of staying in that state, a 10% chance of moving to the ESRD state, and a 5% chance of dying. Each year, patients with ESRD have a 70% chance of continuing in the ESRD state and a 30% chance of dying. Patients who have died have a 100% chance of staying dead.Markov Example: Diabetes PatientsTime step: 1 yearCDESRD0.1D0.050.30.850.71.0probabilities out of any state must sum to 1.0Markov Model ImplementationGenerate a random number (0.0, 1.0)Use random number and current state to generate next stateif state is CD: if rand < 0.1: state  ESRD else if rand < 0.1+0.05: state  D else state  CDelse if state is ESRD: if rand < 0.3: state  D else state  ESRDelse: state  Dnote: need to add up previous probabilitiesImplementation: C++class DiabeticPatient{public: enum State { CD, ESRD, D }; // constructor: set initial state and transition probabilities DiabeticPatient(); // Transition function: changes state void update(); // output functions: simply return current state State output() { return state; } private: State state; // current state double transition_probability[3][3]; // transition table};Implementation: C++ // constructor: set initial state and transition probabilities DiabeticPatient::DiabeticPatient() : state(CD) { transition_probability[CD][CD] = 0.85; transition_probability[CD][ESRD] = 0.10; transition_probability[CD][DEAD] = 0.05; transition_probability[ESRD][CD] = 0.00; transition_probability[ESRD][ESRD] = 0.70; transition_probability[ESRD][DEAD] = 0.30; transition_probability[DEAD][CD] = 0.00; transition_probability[DEAD][ESRD] = 0.00; transition_probability[DEAD][DEAD] = 1.00; }Implementation: C++// Transition function: change state based on current// state and probability parameters.// Each update represents one year. void DiabeticPatient::update() { float r = double(rand())/RAND_MAX; if (r < transition_probability[state][CD]) state = CD; else if (r < transition_probability[state][CD] +transition_probability[state][ESRD]) state = ESRD; else state = D; }Utilizing the SimulationHow would you use this simulationto