Basic Knowledge: Finite-State Machine

State Machine

A Finite-State Machine is a system with explicitly defined states and transitions between the states with the following syntax

• a state is presented by a circle and defines a stable execution point
• a final state is defined by a circle with a double outline
• the state machine defines a single initial state with a triangle
• a transition is presented by an arrow which starts in a state and ends in a state. A transition symbol is an active execution call like a function

Mostly the state name is documented within a state; the arrow of a transition can also be used for documentation.

This example shows a similar state machine with three states that runs from the initial state to a final state (left to right). This example shows the static structure of the state machine, so there is no runtime information within the illustration

Usage and Example

State machines are an useful tool to describe regular expressions and we would like to motivate this concept for explaining the functional principle:

The main goal is to create a system which can check strings that matchs the following criteria: The strings starts with an arbitrary sequence of the letter a or b (the sequence can be empty). After the initial sequence follows a positive number which can be any digit. The end of the digit sequence is a sequence of the letter x with two letters at minimum. All letters within this string can be lower- or upper-case. Some valid example sequences: ab1x, aaabbb169Xx, AaAabbBB972xXxXXXX

Most programming languages define such regular expression in a perl notation or posix notation. We use for the example the posix notation which is defined as:

(a|A|b|B)* [0-9]+ (x|X){2,}

• The first block (a|A|b|B)* defines the different letters and the | defines the or-Operator. At the end the *-operator defines $\geq 0$ elements.
• The second block [0-9]+ defines all elements between 0 and 9 and the +-operator sets the number of elements $\geq 1$
• The third block (x|X){2,} defines similar to the first both letter cases and the {2,} defines the number of elements with $\geq 2$

Based on this definition, it is possible to define a state machine which can check if the string matchs the given structure. During runtime, the string is read character by character and based on the state machine a transition from start state to final state will be found. If the state machine terminates in the error state or on any other state, the string does not match. For example:

• animate state machine with the valid string: aaabbb169XxX
• animate state machine with the non-valid string: AA2b

Petri Net

Based on the static information of the state machine, it can be extended to a petri net, which allows describing agent behaviour during runtime.