Behavioral Modeling with States and Transitions

We try to introduce in this chapter the basic concepts of behavioral system modeling, and at the same time introduce some basic modeling paradigms, such as use cases, sequence diagrams, activity diagrams, different kinds of state machines - namely Markov models, Labelled Transition Systems (LTS), Accepting Automata, Input-Output Automata (IOA), Finite State Machines (FSM), and extended state machine models, such as UML State diagrams.

Note that we distinguish in the following between properties that have a "formal" meaning, and other properties that remain informally described (that means they are essentially described in english (or some other natural language) - as a complement to the formal model.

Actions versus States

Choice between state-oriented and action-oriented models - the nature of transitions

As an example, we consider the process by which an artist creates a wood sculpture (I remember, I did this when I was young): (1) the artist comes up with an idea of a sculpture, (2) s/he takes a piece of wood and prepares an outline of the sculpture, (3) the sculpture is refined in detail, and finally, (4) the sculpture is polished (and can be admired). Here are several representations of this process:

Note that diagrams (a), (b) and (c) have exactly the same meaning, while diagram (d) shows the process from another perspective, namely from the point of view of the object that is manipulated. In diagrams (a) through (c), the transitions between the activities/states are short, while some longer time periods are spent during the activities shown in the diagram (or the actions implied by the name of the states - in diagram (c)). In the perspective of the manipulated object (diagram (d)), the transitions take some longer time, while the states represent milestones - identifyable states of the object during the creating process. I would say that the diagrams (a) through (c) are action-oriented models, while diagram (d) is state-oriented. If we compare diagrams (c) and (d), we see that actions become states and states become actions. It is important to note that these two approaches can be used for describing the same reality. Which of these two approaches is better depends on the purpose of modeling.


In other words:

The same reality can also be represented by the UML Activity diagram below including object (data) flow. This diagram includes both views, the action-oriented and the state-oriented one. Here the data objects (represented by the rectangulars) represent the sculpture in its different states. Note: Here the transitions are associated with data objects that are produced by one action and consumed by the next action - they are actually inputs and outputs for these actions, namely the activities in the diagram.

sculpture with object flow

Agents, components and resources

Activity diagrams and UCMs can also be used to define agents. These agents may represent actors, the system, system components or resources that are involved in the identified activities. In UML Activity diagrams, these entities are called "swimlanes", while in UCMs, they are called "components". In practice, these entities often represent actors outside the system boundary, or components that are part of the system. These entities represent resources that are dedicated to a given instance of the Activity diagram, or that are shared between several instances. They are sometimes called "agents" and one may distinguish active and passive agents. For instance, human actors must be considered active agents, also reactive systems that take initiative for performing certain actions. Object instances that provide a method call interface are passive, since they do not take own initiatives. Here is an example of a UML Activity diagram including swimlanes and object flow. (Note: the horizontal thick line at the top of the customer swimlane is probably an error and should be a rectangle reading "o:Order [prepared]").

activity diagram example

Here is a short comparison of Activity diagrams and UCMs and the concepts that they allow to specify

Complementary readings

Different semantics for state transition models

Meaning of round symbols

As discussed above, a model represented as a set of state with transitions between these states may have different meaning. (Note: "meaning" is also called "semantics"). In general, each state and each transition has a name to distinguish it from the other entities in the model. As shown by the example above, there are basically two semantics for state transition models:

Triggering of transitions

There are also different semantics concerning the triggering of transitions, that is the question, "under which condition is a transition initiated ? "

Different kinds of interactions with the environment

There are different versions of state-oriented semantics concerning the interactions with the environment. In this course, we mention the following:

Simple examples

Markov model

The following is an example of a system that may fail and can be repaired. If one adds to each transition a transition rate (probability that the transition will fire within the next time unit if the system is in its starting state), then one obtains a Markov model which allows the prediction of the probability that the system is (at any given time) in a particular state. Example: What is the availability of the system shown above if the transition rate of the "failed" transition is 1/1000 and the rate of "repaired" is 1/100 ?

Markov model

LTS with rendezvous communication

Here is a very simple example. The model of an interview involving three agents and several actions that are performed in a prescribed order: The collaboration involves three agents, the company director, the journalist, and the secretary. It includes the following actions: a welcome shake hands, interview talk, and a good-bye jointly performed by the director and the journalist; and talk with the secretary, and secretary entering or leaving joinly performed by the director and the secretary (we assume that the director gives the permission for the interruption by the secretary, and indicates when it is time to leave). A reasonable sequencing of these actions is defined by the state diagram (a)), which also represents the order of actions of the company director. Diagrams (b) and (c) describe the behavior of the agent and the secretary, respectively. We note that the interview is interrupted when the secretary enters the room until s/he leaves again.


Note: In this example (and when using LTS models, in general), one uses an state-oriented modeling approach where the actions are modeled as transitions, and not as "activities" or "states". In fact, these transitions here represent collaborations between several agents. The LTS transitions may also represent simple interactions between the described system and its environment, as we will discuss below for clent-server system modeling. This approach is similar to diagram (d) of the artist example, although in that diagram the actions are not explicitly mentioned, since the emphasis was on the states of the object.

Semantics of LTS systems: Given an LTS, one is usually interested in all the sequences in which the transitions of the LTS can be executed, starting from the initial state of the LTS and ending in some final state. One calls execution trace the corresponding sequence of transition labels.

LTS example

Another LTS example: the Hotel example

Accepting Automata

The ability of a state machine to define a set of acceptable traces is used for the analysis of natural and programming languages. Let us consider an agent with the behavior of the Accepting Automaton (c) shown above (we assume that the upper right state is the only accepting state). This machine accepts as traces any string of characters that represent a valid decimal number without a leading zero. If we combine this machine with a character reader that always offers as input to the machine the next character to be read from an input file, then we obtain a system that has an non-specified reception is the read character string is not a valid decimal number, and if at the end of the input string the automata is in its accepting state, then the input string is valid. This will be further discussed in Section 2 of this course.

Client-server systems

Let us now consider collaboration between an active agent and a passive agent, such as in the case of a client-server system. The server provides an interface that allows the client to call certain methods. Here the client initiates the interactions.

Combination of input and rendezvous

Sometimes, in a client-server model (where it is clear which side initiates the interaction) one has rendezvous semantics for the initiation of the interaction, that is, the passive server may prevent an interaction from happening if it is in a state where this interaction is not possible. For instance, in a coffee machine, the coin insert may be blocked when no coffee is left in the machine, or the coffee buttom could be disabled until enough money is inserted. As an example, we consider a door which can be modeled by the state diagrams below. Clearly, the transition open is not possible in the state lock (the door in this state is blocked for this transition).


Asynchronous Input-Output communication

In asynchronous communication, there is no time instance where both parties are involved in the communication - usually, the sending agent may get involved in other activities while the message propagates to its destination.

See example of a Coffee Machine.

Different variants of state machines with the same semantics

In the following, we show several state machine models for an automated teller machine (ATM). Figures (a) and (b) relatively abstract, they do not explicitly identify the inputs and outputs of for the system. Diagram (a) is a UML Activity diagram and (b) is an LTS.

ATM (a) and (b)ATM (c)ATM d,e,f

The other models explicily identify inputs and outputs.

Extended state machine models

The formal models of FSM or IOA are characterized by a finite set of possible inputs, a finite set of possible outputs, and a finite number of state, as well as an initial state and the transition function (as discussed above). For most modeling tasks, such formal models are too restrictive. For instance, in the example of the ATM shown above, one has already introduced certain extensions: there are a large number of possible NIP values. In the formal FSM model, one would either have to ignore these different values, or introduce a separate NIP-message for each possible NIP value. One also assumes that there is a way to determine whether the NIP is OK or not. What about modeling the fact that the card is not returned in case that 3 wrong NIP values were provided ?

In the examples above, these extensions were informally modeled by using some names and/or comments that suggest certain properties. However, it would be better to formalize these aspects. For this purpose, state machine modeling paradigms are often extended by introducing the following formal concepts:

Example: extended state machine model of an ATM

Below is the example of an ATM model that includes some more formal specification of properties using the extended formalism described above, using the notation of UML State diagrams. It is assumed here that the machine has two state variables:

It is also assumed that the input amount_entered contains an integer parameter, called request, representing the number of cents the user wants to withdraw, and that the output display contains a String parameter which contains the text to be displayed to the user. The elements refering to these variables or interactions, in the following state machine model, are written in bold. The notation for writing the enabling conditions and expressions for assignments or output parameters is usually borrowed from the language that is used by the UML tool for the generation of executable code (in order to simplify this generation process). In the example below, we have used Java syntax.

ATM (g)

Features of UML Activity diagrams and State diagrams

Several languages for modeling state machines, based on the above concepts, have been developed, and some have been standardized. CASE tools have been developed for several of these languages. They help in editing models, allow simulated execution and the generation of corresponding sequence diagrams (for the verification and validation of the specification) and for automatic generation of code which provides an implementation of the model or can be integrated with other software components. We mention in particular the following languages:

UML state diagramcourse

Complementary readings

Real-time modeling

The modeling paradigms discussed above (except for the Markov models) only describe the order in which the different interactions at the different interfaces may occur during the execution of the system. In many cases, there are also performance requirements that must be met:

If the requirements of a system include statistical or hard real-time performance properties, one says that the system is a real-time system. Most of the time, these systems are reactive systems (see above).

Modeling paradigm (a): a real-time variable NOW

In many situations, a variable representing the current real-time is available (e.g. provided by the operating system), often called "now". The time of a modeled event may recorded by copying now into a local variable. Then a later transition of the model may include an enabling condition which states the the current real-time (e.g. now) should be equal to the stored time value plus some given delay duration.

Modeling paradigm (b): Timed automata

The formal model of Timed Automata (that is, timed state machines) considers that a state machine is associated with a certain number of clocks that are always running. A clock may be reset to zero by a transition (in order to show, in the future, the time that has passed since that transition). Then other transitions may include enabling conditions that specify some constraints for one or several clocks, each constraint requiring that the clock value be within a given range of values. Many CASE tools have been developed for this kind of modeling paradigm. (Not further discussed in this course).

Modeling paradigm (c): Timers and time-outs

SDL has adopted the modeling approach by which a state machine may be associated with a certain number of timers (appearently this is not supported by normal UML). Timers are clocks that normally do not run (in the inactive state), but they can be set to start running until they reach a given time value, at which point they will generated a so-called "time-out" and stop running. They may also be reset to go back to the idle state before the time-out is reached. The occurrence of a time-out is handled by the state machine as an event. Therefore the specification of the machine should include appropriate transitions for the cases that some of its times produces a time-out. Here is a state diagram of a timer:

timer semantics

The following is an example of a behavior presented in the SDL dialect of UML (called transition-oriented notation). It includes on timer called door_timeout which is set before the system enters the Opening state. A time-out occurs if the Opened signal is not received after 10 time units. If the Opened signal is received before that time, the timer is set again to a new value and a time-out will occur if the Closed signal is not received within 30 time units.

timer example

Course notes - Gregor v. Bochmann - University of Ottawa. Created January 2011, last update: January 13,  2015