Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Design of Embedded Systems Models Validation and Synthesis EE 249 Lecture 4a Prof Dr Reinhard von Hanxleden Christian Albrechts Universita t Kiel Department of Computer Science Real Time Systems and Embedded Systems Group 13 September 2007 Last compiled 4th October 2007 18 45 hrs Statecharts Fall 2007 EE 249 Slide 1 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Overview Finite State Machines Finite Automata Moore Machines Mealy Machines Statecharts Stateflow SyncCharts Safe State Machines Fall 2007 EE 249 Slide 2 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Finite Automata Formally a finite automaton is defined as a five tuple Q q0 F where Q 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 input symbol a the new state q a that arises as reaction on the execution of a in state q Thanks to Willem Paul de Roever and Kai Baukus for providing part of the following material Fall 2007 EE 249 Slide 3 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines State Diagram For each state the possible reactions to input that arrives in that state is specified by a transition to other states Fall 2007 EE 249 Slide 4 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Extensions I I Restriction of these kind of automata as defined above they have an input alphabet but not an output alphabet There are two ways to extend the above model with output 1 Output can be associated with a state a so called Moore machine 2 or with a transition a so called Mealy machine I I A Moore machine is a 6 tuple Q q0 where Q q0 are the same as in the definition of the finite automaton is the output alphabet and Q is the output function A Mealy machine is also a 6 tuple Q q0 but now is a function from Q to Fall 2007 EE 249 Slide 5 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Example Moore Machine Idle action initialize enter coin Ready enter coin Emitting cup action emit cup cup emitted cup removed Pouring coffee action pour coffee I Moore machine output is associated with every state I Mealy machine q a gives output associated with the transition of state q on input a Fall 2007 EE 249 Slide 6 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Serial Addition Moore Machine 0 1 1 0 or 0 1 0 0 0 1 or 1 0 0 0 1 1 1 1 0 0 0 0 1 0 carry 0 carry 1 1 1 1 1 1 0 1 0 0 1 or 1 0 Fall 2007 EE 249 Slide 7 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Serial Addition Mealy Machine 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 carry 0 0 1 0 1 0 0 1 1 1 carry 1 Fall 2007 EE 249 Slide 8 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Disadvantages I They have no structure There is no strategy for their top down or bottom up development I State transition diagrams are flat i e without a natural notion of depth hierarchy or modularity I State transition diagrams are uneconomical concerning their transitions think for instance of a high level interrupt Fall 2007 EE 249 Slide 9 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Interrupt Transition They are not economical w r t transitions when one event has all transitions as a starting point as in case of interrupts Interrupt state Fall 2007 EE 249 Slide 10 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Finite Automata Moore Machines Mealy Machines Disadvantages cont d I Concerning the states state transition diagrams are even very uneconomical Exponential blow up I They are not economical w r t parallel composition Exponential growth in the number of states when composed in parallel I The nature of state transition diagrams is inherently sequential and so parallelism can t be represented in a natural way Fall 2007 EE 249 Slide 11 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Hierarchy Orthogonality Broadcast Time in Statecharts Overview Finite State Machines Statecharts Hierarchy Orthogonality Broadcast Time in Statecharts Stateflow SyncCharts Safe State Machines Fall 2007 EE 249 Slide 12 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Hierarchy Orthogonality Broadcast Time in Statecharts Statecharts I We need a formalism for the hierarchical development and refinement of Mealy machines I This is provided by Statecharts invented by David Harel 1987 I Statecharts display hierarchy and structure and enable hierarchical development I In the following will illustrate this with the example of a television set with remote control I The Statecharts used in this lecture follow the syntax of the original Statecharts as invented by Harel and as supported by the STATEMATE toolset Fall 2007 EE 249 Slide 13 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Hierarchy Orthogonality Broadcast Time in Statecharts First Concept Hierarchy I Hierarchy or depth in states and interrupts I This is achieved by drawing states as boxes that contain other boxes as sub states I The television set can be in two states ON and STANDBY Switching between them is done by pushing the on and off buttons generating the on and off events Fall 2007 EE 249 Slide 14 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines Hierarchy Orthogonality Broadcast Time in Statecharts Zooming into ON In state ON the tv set can be in two sub states NORMAL and VIDEOTEXT The arrow leading to NORMAL specifies which sub state should be entered when the higher level state ON is entered namely NORMAL this state is also called the initial state within ON Note To be complete one of the states ON and OFF would also need to be labeled as initial state at top level Fall 2007 EE 249 Slide 15 Finite State Machines Statecharts Stateflow SyncCharts Safe State Machines
View Full Document
Unlocking...