Finite State Automata

1 Sample Signal Generator

The following is an example of a simple generator model that produces periodic sampling signals. The state transitions of the finite state automaton are hidden inside the implementation of the built-in function sample.

2 Clocked-State Machines

Starting with the Modelica language version 3.3, constructs for directly creating state machines to model finite state automata applications are available in the Modelica language. This section gives a short introduction to the use of such clocked state machines.

There are many similarities between finite state automata and clocked state machines, but also some differences:

1) Self-transitions are not needed in Modelica clocked state machines. The reason is that a clocked state machine stays in its current state if the transition conditions to other states are not fulfilled.

2) Transitions in state machines are made at clock ticks whereas transitions in finite state automata happen at the arrival of events. However, events can be modeled by Boolean transition conditions which may become true and cause a transition at the next clock tick.

We first define a simple state machine model called CountingStateMachine1. It has two states, the initial state state1 and a second state state2. The default clock with interval 1 applies since there is no explicit clock declaration.

It has a counting variable cn, initially zero, which is declared inner at the model level, and outer in each state so that it can be referred to locally within each state. In state1, cn is increased by 1 at each clock tick, whereas in state2, cn is decreased by 3 at each clock tick. When the transition condition for the first transition fulfills previous(cn>7)=true (since immediate=false) there is a transition to state2 according to the transition( ) equation.

In state2, when the condition previous(cn<3)=true is fulfilled, there is a transition back to state1.

3 Simple Server

One of the simplest possible examples of an input/output process modeled as a finite state automaton is the simple server.The simple server finite automaton has two states, denoted Active and Passive, and a set of values {Start, Done} which is an alphabet of two symbols. The system becomes active and provides some service after receiving a Start event. After finishing the service item, the system emits a Done event and returns to the Passive state.

4 Assignment Recognizer

The assignment regocnizer is an example of a common application, a string acceptor in lexical analysis of text, typically in compiler frontends. Input events are the arrival of characters in an input stream.