Finite State Machines k State Transition Diagrams Peter A. Smith & Alexander M. Fedorec Three Different Views of a System Structural Model (e.g. entity, class, deployment diagrams...) Showing the components, subsystems, modules, entities or objects and how are they related/connected Functional Model (e.g. use case model, DFD, HIPO) Showing the capabilities and functions required of the system. Normally expressed in terms of inputs, outputs and processes Behavioural Model (e.g. activity, state diagram) Shows system dynamics. Represents how the system changes state/mode and the events and conditions that cause the changes to happen. A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.2 Systems Behaviour Systems can classified by the way they change: Discrete Finite number of discrete internal states,

Finite number of distinct inputs and outputs. Operates in discrete time steps Measures map to natural numbers (positive integers) Continuous Internal states, inputs and outputs continuously variable Measures map to the real numbers e.g.analogue watch vs. digital watch coins in a purse vs. fluid in a bottle? A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.3 Finite State Machines An FSM describes a system behaviourally as Finite number of discrete states and Finite number of permissible transitions between states e.g. Traffic lights 3 lights each of which can be in one of two states (on or off) 8 possible states (all lights off, one on, any two on, all three on) Only 4 legitimate states and 4 valid transitions: Red on Red & Amber Green Amber on Red Can be modelled as State Transition Graph (STG)) States labelled circles or rounded boxes. Each circle represents one possible state that the FSM can be in. Transitions Arcs connecting states labelled with events that trigger state transitions Also known as Finite State Automata (FSAs) A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.4

Example FSM: Traffic Lights All Possible States and Transitions And so on. Red & Amber Red Green & Red All lights off Amber All lights on Green Green & Amber Q. Given 8 states how many possible transitions are there? A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.5 Example FSM: Traffic Lights Valid States and Legal Transitions Red & Amber Red Green & Red All lights off

All lights on Green Amber Green & Amber A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.6 FSMs with Output: Transducers State transitions are triggered by inputs or caused by events (e.g. pushing a button, a clock tick, change temperature) input/event POWER shutdown idle POWER state F1 help new state transition When machines change state they normally do something and the actions often generate output. shutdown

light off POWER POWER state idle light on F1 help Display stay calm output/action Automata with input and output are sometimes called transducers because of their connection to electronics A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.7 Example FSM: Traffic Lights Valid States, legal transitions and output S1 Red light S3 Amber A.M.Fedorec 2/12/20 05:03 AM S2 Red + Amber S4

Green State Output S1 S2 S3 S4 Red light Red + Amber lights Green light Amber light Stop Ready Go Caution Note: system greatly simplified. Real system will have input signals: Timing devices Pedestrian buttons Road induction loops Traffic cameras CSN9901FSA.8 Other Example Finite State Machines Car injection systems

Communications systems Digital Computers Computer language translation e.g. from high level to machine code A.M.Fedorec 2/12/20 05:03 AM Electronic Games Fetch-execute cycle Operating systems Vending machines Washing machines CSN9901FSA.9 Mealy & Moore Machines Transducer output can either be on the state nodes (Moore machine e.g. traffic lights example) or on the transition arcs (Mealy machine). Mealy and Moore machines can be shown to be equivalent: State (q4 ) a q4 t b c Output or action (t)

a/t b/t q4 c/t Input or state changing event (c ) A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.10 FSM with one input and one output. FSM asserts its output (i.e. outputs a 1) when it recognizes the input bit sequence: "1011". Machine will keep checking for the proper bit sequence and does not reset to the initial state after it has recognized the string. E.g. the input string = "..1011011..." will cause the output to go high twice: = "..0001001.." FSM implemented as a Moore Machine (output on state): 0 1 1 S0 0 1 ...1 0 S1 0 ...10

S2 0 1 0 ...101 0 A.M.Fedorec 2/12/20 05:03 AM 1/0 ...1 ...1011 S4 1 0 FSM implemented as a Mealy Machine (output on transition): 0/0 1/0 S0 1 S3 0 S1 0/0 0/0

...10 S2 1/0 1/1 0/0 ...101 S3 CSN9901FSA.11 BACKGROUND INFORMATION FOR INTREST UML Notation For FSMs Action event off hook Idle do: play dial tone Active on hook disconnect Action on state A.M.Fedorec 2/12/20 05:03 AM Note UML is not part of the CSA syllabus

CSN9901FSA.12 BACKGROUND INFORMATION FOR INTREST UML Notation for FSMs Statechart Diagrams Initial State Action event State off hook / play dial tone Idle Active on hook disconnect State transition Final State A.M.Fedorec 2/12/20 05:03 AM Action on state transition Note UML is not part of the CSA syllabus CSN9901FSA.13 BACKGROUND INFORMATION FOR INTREST

Example Telephone on ho o Idle Event/action k off hook / play dial tone on hook PlayingDialTone on hook connected digit digit Talking Connecting Dialing complete on hook Note UML is not part of the CSA syllabus A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.14 BACKGROUND INFORMATION FOR INTREST

Nested States in UML off hook / play dial tone Idle Active Initial state on hoo k PlayingDialTone digit Talking connected digit Connecting Dialing complete Note UML is not part of the CSA syllabus A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.15 State Tables A FSM can be expressed in tabular form as the (state, input) pairs in terms of the next state, and action for each

e.g. A circuit starts takes as input a string of 0s and 1s. After it inputs its first 1 it will output a 1 on the second, fourth, sixth... 0 it inputs until it inputs another 1 when it will go back to the reset state. State Table 0/- reset 1/0 1/0 1/0 0/0 q1 q2 0/1 State Diagram A.M.Fedorec 2/12/20 05:03 AM Current state Input = 0 Input = 1 R R, - q1, 0 q1

q2, 0 R, 0 q2 q1, 1 R, 0 1 Next state, output given input = 0 CSN9901FSA.16 FSM Example (to do on whiteboard) A coffee vending machine dispenses coffee at 20p per cup. It accepts 5p, 10p and 20p coins No change is given Inexhaustible supply of water cups, coffee powder etc. Modifications: 1. A return coins button may be pressed at any time 2. Tea is dispensed at 25p per cup A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.17 Coffee Machine Example returnCoins 20p Accept 5p, 10p or 20p coins,

Dispense coffee when input 20p Refund if return coin button pressed / coffee returnCoins / refund Actions coffee machine dispenses coffee refund machine returns coins / refund Events 5p 10p error 20p returnCoins q0 5p 10p q1 5p 10p / coffee 5p q2 A.M.Fedorec 2/12/20 05:03 AM / coffee

10p q3 10p InsufficientMoney Basic States q0 no money in machine q1 5p in machine q2 10p in machine q3 15p in machine error more than 20p in machine InsufficientMoney 5p customer enters 5p coin customer20p enters 10p coin customer enters 20p coin customer presses return button Input State 5p 10p 20p

returnCoins q0 q1 q2 q0 , coffee q0 q1 q2 q3 error q0 , refund q2 q3 q0 , coffee error q0 , refund q3 q0 , coffee

error error q0 , refund error error error error q , refund 0 CSN9901FSA.18 Minimal Tables If given the same inputs two separate states produce the same outputs and take the system to the same next state then one is redundant 1/0 0/0 qa qc 1/0 0/0 Input = 0 Input =

1 qa qb, 1 qc, 0 qb qa, 0 qb, 0 qc Redundant qa, 0 qb, 0 qb 0/1 1/0 1/0 0/0 qa qb 0/1 Given same input Two separate states Same next state and output 1/0

A.M.Fedorec 2/12/20 05:03 AM Current state Current state Input = 0 Input = 1 qa qb, 1 qb, 0 qb qa, 0 qb, 0 CSN9901FSA.19 BACKGROUND INFORMATION FOR INTREST ONLY Subjects of State Diagrams in UML All classifiers in UML have identity, state and behaviour and can therefore be represented by a statechart (however dumb entity objects may stay in only one state for their entire life, eg. a static string) Examples: Use Cases

Student registering interest for a job with the IT placement office involves recording their details if it is the first time they have applied for a job Classes Student object changes from level 5 to sandwich placement or level 6 etc. Other Examples: Windows Edit-Paste is only valid if there is something in the clipboard Devices, Controllers, Transactions, Application, Coordinators A.M.Fedorec 2/12/20 05:03 AM Note UML is not part of the CSA syllabus CSN9901FSA.20 BACKGROUND INFORMATION FOR INTREST Concurrent States in UML maintain Idle Maintenance Testing Testing devices Commanding Self

Diagnosis keyPress Waiting Command [not continue] [continue] Note UML is not part of the CSA syllabus A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.21 ACKGROUND INFORMATION FOR INTREST ONLY Concurrent States in UML Example 2 NormalOperation EW Green after 40 sec EW Amber after 5 sec EW Red after 35 sec NS Red after 45 sec

NS Green after 30 sec NS Amber after 5 sec https://users.cs.jmu.edu/foxcj/Public/ISED/slides/Ch13B.ppt 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley Note UML is not part of the CSA syllabus A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.22 Non-Deterministic FSA In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. 0,1 P 1 Q Nondeterministic since in state p reading a 1 can lead to p or to q. 2/12/20 05:03 AM From: Nondeterministic finite automaton, https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton, accessed Feb 2016

CSN9901FSA.23 Summary Systems have state Events such as inputs cause the system to change state State change may trigger an output on the state transition or in the new state. A state transition graph describes the legal states and valid transitions a system can make This can also be described with a state table A.M.Fedorec 2/12/20 05:03 AM CSN9901FSA.24 Further Reading For Computer Scientists Cohen, D., Introduction to Computer Theory 2e, Wiley, 1997 For Software Engineers Harel, D., Politi, M. Modeling Reactive Systems with Statecharts, McGraw-Hill, 1998 For CSNE Pedroni, V.A., Finite State Machines in Hardware: Theory and Design, MIT, 2013 For fun: Stefan Hollos, S., Hollos, J.R., Finite Automata and Regular Expressions: Problems and Solutions, Abrazol Publishing, 2013 2/12/20 05:03 AM CSN9901FSA.25