Unformatted text preview:

Finite State MachinesFinite AutomataMoore MachinesMealy MachinesStatechartsHierarchyOrthogonalityBroadcastTime in StatechartsStateflowSimulink InterfaceSemanticsSyncCharts (Safe State Machines)StatesTransitionsConnectorsEsterel StudioFinite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Design of Embedded Systems: Models, Validationand Synthesis (EE 249)—Lecture 4aProf. Dr. Reinhard von HanxledenChristian-Albrechts Universit¨at KielDepartment of Computer ScienceReal-Time Systems and Embedded Systems Group13 September 2007Last compiled: 4th October 2007, 18:45 hrsStatechartsFall 2007 EE 249 Slide 1Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesOverviewFinite State MachinesFinite AutomataMoore MachinesMealy MachinesStatechartsStateflowSyncCharts (Safe State Machines)Fall 2007 EE 249 Slide 2Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesFinite AutomataFormally a finite automaton is defined as a five tuple(Q, Σ, δ, q0, F ) whereQ is a finite set of states,Σ is the input alphabet,q0∈ Q is the begin state (initial state),F ⊆ Q is the set of final states,δ : Q × Σ → Q is the transition function.The transition function gives for every state q and every inputsymbol a the new state δ(q, a) that arises as reaction on theexecution of a in state q.Thanks to Willem-Paul de Roever and Kai Baukus for providing part of the followingmaterialFall 2007 EE 249 Slide 3Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesState DiagramFor each state, the possible reactions to input that arrives in thatstate is specified by a transition to other states.Fall 2007 EE 249 Slide 4Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesExtensionsIRestriction of these kind of automata as defined above: theyhave an input alphabet but not an output alphabet.IThere are two ways to extend the above model with output:1. Output can be associated with a state (a so called Mooremachine)2. or with a transition (a so called Mealy machine).IA Moore machine is a 6-tuple (Q, Σ, ∆, δ, λ, q0) whereQ, Σ, δ, q0are the same as in the definition of the finiteautomaton,∆ is the output alphabet andλ : Q → ∆ is the output function.IA Mealy machine is also a 6-tuple (Q, Σ, ∆, δ, λ, q0) but nowλ is a function from Q × Σ to ∆.Fall 2007 EE 249 Slide 5Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesExample: Moore MachineReadycup emittedenter coinIdleenter coincup removedaction: initializeEmitting cupaction: emit cupPouring coffeeaction: pour coffeeIMoore machine: output λ is associated with every stateIMealy machine: λ(q, a) gives output associated with thetransition of state q on input a.Fall 2007 EE 249 Slide 6Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesSerial Addition: Moore Machine(1,0)(1,1)(0,0)0110(1,1)(0,0)(0,0)(1,1)(0,0)(1,0)(0,1)(1,1)(1,0) or (0,1)(0,1) or (1,0) (0,1) orcarry: 0carry: 1Fall 2007 EE 249 Slide 7Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesSerial Addition: Mealy Machine(0,0)/0(1,0)/1(0,1)/1(1,1)/0(0,0)/1(0,1)/0(1,0)/0(1,1)/1carry: 0 carry: 1Fall 2007 EE 249 Slide 8Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesDisadvantagesIThey have no structure. There is no strategy for theirtop-down or bottom-up development.IState-transition diagrams are “flat”, i. e., without a naturalnotion of depth, hierarchy or modularity,IState-transition diagrams are uneconomical concerning theirtransitions; think for instance of a high-level interruptFall 2007 EE 249 Slide 9Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesInterrupt TransitionThey are not economical w. r. t. transitions, when one event has alltransitions as a starting point as in case of interrupts:Interrupt stateFall 2007 EE 249 Slide 10Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)Finite AutomataMoore MachinesMealy MachinesDisadvantages (cont’d)IConcerning the states, state-transition diagrams are even veryuneconomical: Exponential blow-upIThey are not economical w. r. t. parallel composition:Exponential growth in the number of states when composedin parallel.IThe nature of state-transition diagrams is inherently sequentialand so parallelism can‘t be represented in a natural way.Fall 2007 EE 249 Slide 11Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)HierarchyOrthogonalityBroadcastTime in StatechartsOverviewFinite State MachinesStatechartsHierarchyOrthogonalityBroadcastTime in StatechartsStateflowSyncCharts (Safe State Machines)Fall 2007 EE 249 Slide 12Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)HierarchyOrthogonalityBroadcastTime in StatechartsStatechartsIWe need a formalism for the hierarchical development andrefinement of Mealy machines.IThis is provided by Statecharts, invented by David Harel(1987)IStatecharts display hierarchy and structure, and enablehierarchical developmentIIn the following, will illustrate this with the example of atelevision set with remote controlIThe Statecharts used in this lecture follow the syntax of theoriginal Statecharts, as invented by Harel, and as supported bythe STATEMATE toolsetFall 2007 EE 249 Slide 13Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)HierarchyOrthogonalityBroadcastTime in StatechartsFirst Concept: HierarchyIHierarchy or depth in states, and interrupts.IThis is achieved by drawing states as boxes that contain otherboxes as sub-states.IThe television set can be in two states: ON and STANDBY.Switching between them is done by pushing the on and offbuttons, generating the on and off events:Fall 2007 EE 249 Slide 14Finite State MachinesStatechartsStateflowSyncCharts (Safe State Machines)HierarchyOrthogonalityBroadcastTime in StatechartsZooming into ONIn state ON, the tv set can be in two sub-states: NORMAL andVIDEOTEXT:The −→ arrow leading to NORMAL specifies which sub-stateshould be entered when the higher level state ON is entered,namely NORMAL;


View Full Document

Berkeley ELENG C249A - Lecture Notes

Documents in this Course
Load more
Download Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?