The article discusses simple finite state machines and their implementation in C++ using switch constructs, runtime tables and the Boost Statechart library.
Introduction
Roughly speaking, a Finite State Machine, through the eyes of the user, is a black box into which something can be transferred and something can be received from there. This is a very convenient abstraction that allows you to hide a complex algorithm, and finite state machines are also very efficient.
Finite state machines are depicted in the form of diagrams consisting of states and transitions. Let me explain with a simple example:
As you probably guessed, this is a state diagram of a light bulb. The initial state is indicated by a black circle, transitions by arrows, some arrows are labeled - these are events after which the machine goes to another state. So, immediately from the initial state, we find ourselves in the state Light Off- the lamp does not light up. If you press the button, the machine will change its state and follow the arrow marked Push Button, in a state Light On- the lamp is on. You can move from this state, again following the arrow, after pressing the button, to the state Light Off.
Transition tables are also widely used:
Practical application of automatic machines
Finite state machines are widely used in programming. For example, it is very convenient to imagine the operation of a device in the form of an automatic machine. This will make the code simpler and easier to experiment with and maintain.
Also, finite state machines are used to write all kinds of parsers and text analyzers; with their help, you can effectively search for substrings; regular expressions are also translated into the finite state machine.
For example, we will implement an automaton for counting numbers and words in text. To begin with, let's agree that a number will be considered a sequence of numbers from 0 to 9 of arbitrary length, surrounded by whitespace characters (space, tab, line feed). A word will be considered a sequence of arbitrary length consisting of letters and also surrounded by whitespace characters.
Let's look at the diagram:
From the initial state we get to the state Start. We check the current character, and if it is a letter, then we go to the state Word along the arrow marked as Letter. This condition suggests that in at the moment we consider the word, analysis of further symbols will either confirm this assumption or refute it. So, consider the next character, if it is a letter, then the state does not change (note the circular arrow marked as Letter). If the character is not a letter, but corresponds to a whitespace character, then this means that the assumption was correct and we found the word (we follow the arrow Space in a state Start). If the character is neither a letter nor a space, then we made a mistake in the assumption and the sequence we are considering is not a word (follow the arrow Unknown in a state Skip).
Able to Skip we are there until a whitespace character is encountered. After a gap has been detected, we follow the arrow Space in a state Start. This is necessary to completely skip a line that does not match our search pattern.
After entering the state Start, the search cycle repeats from the beginning. The number recognition branch is similar to the word recognition branch.
Automaton using switch instructions
The first is possible states:
After which we iterate over the line, slipping the current symbol into the machine. The machine itself is a switch instruction that first performs a transition to the section of the current state. Inside the section there is an if-else construct, which, depending on the event (an incoming symbol), changes the current state:
| const size_t length = text.length(); for (size_t i = 0 ; i ! = length; ++ i) ( const char current = text[ i] ; switch (state) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) else if (std:: isalpha (current) ) ( state = State_Word; ) break ; case State_Number: if (std:: isspace (current) ) ( |
Here we look at the diagram - the current state Number, event Space(a space character is encountered), which means the number is found:
| FoundNumber() ; state = State_Start; ) else if (! std::isdigit(current) ) ( state = State_Skip; ) break ; case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (current) ) ( state = State_Skip; ) break ; case State_Skip: if (std::isspace (current) ) ( state = State_Start; ) break ; ) ) |
Result:
High efficiency
Ease of implementation for simple algorithms
- Difficult to maintain
Runtime Interpretation
The idea of this approach is simple - you need to create a transition table, fill it, and then, when an event occurs, find the next state in the table and make the transition:
| enum Events ( Event_Space, Event_Digit, Event_Letter, Event_Unknown ) ; void ProcessEvent(Events event) ; ... struct Transition ( States BaseState_; Events Event_; States TargetState_; ) ; void AddTransition(States fromState, Events event, States toState) ; ...typedef std::vector< transition>TransitionTable; TransitionTable Transitions_; States CurrentState_; |
Filling out the table:
| AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip) ; AddTransition(State_Number, Event_Unknown, State_Skip) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ; |
It turned out quite clearly. The price for clarity will be slower operation of the machine, which, however, often does not matter.
So that the machine, when certain events occur, can notify some code, you can add it to the structure with information about the transition ( Transition) function pointer ( Action), which will be called:
| typedef void (DynamicMachine:: * Action) () ; struct Transition ( States BaseState_; Events Event_; States TargetState_; Action Action_; ) ; ... void AddTransition(States fromState, Events event, States toState, Action action) ; ...AddTransition(State_Number, Event_Space, State_Start, & DynamicMachine::FoundNumber) ; |
Result:
Flexibility and visibility
Easier to maintain
- Less performance compared to switch blocks
Interpretation of execution time. Speed optimization
Is it possible to combine visibility with speed? It is unlikely that it will be possible to make an automatic machine as efficient as an automatic machine based on switch blocks, but it is possible to close the gap. To do this, you need to build a matrix from the table, such that to obtain information about the transition, you do not need to search, but make a selection by state and event number:
The result is achieved at the expense of memory consumption.
Result:
Flexibility, visibility
Effective
- Memory consumption (most likely unimportant)
Boost Statechart
We discussed several ways to implement a state machine yourself. For a change, I propose to consider a library for building machines from Boost. This library is very powerful; the capabilities offered allow you to build very complex finite state machines. We will look at it quite quickly.
So, first we define the events:
| namespace Events ( struct Digit : boost::statechart::event< Digit>( ) ; struct Letter : boost::statechart::event< Letter>( ) ; struct Space: boost::statechart::event< Space>( ) ; struct Unknown : boost::statechart::event< Unknown> { } ; } |
The machine itself (note that the second template parameter is the initial state):
| struct Machine: boost::statechart::state_machine< Machine, States:: Start > { } ; |
And the states themselves. Inside the states, it is necessary to determine the type that describes the transitions ( reactions), and if there are several transitions, then list them in the boost::mpl::list type list. Second template parameter simple_state– type describing the machine. Transitions are described by the parameters of the transition template, a pair Event - Next State:
| namespace States ( struct Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reactions; ) ; struct Number : boost::statechart::simple_state< Number, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Letter , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reactions; ) ; struct Word: boost::statechart::simple_state< Word, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Digit , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reactions; ) ; struct Skip: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >reactions; ) ; ) |
The machine is built, all that remains is to initialize it and you can use it:
| Machine machine; machine.initiate(); ... machine.process_event(Events::Space()); |
Result:
Flexibility, expandability
- Efficiency
Performance
I wrote a test program to check the performance of the constructed machines. I ran a ~17 MB text through the machines. Here are the results of the run:
Loading text Text length: 17605548 bytes 0.19 s Running BoostMachine Words: 998002, numbers: 6816 0.73 s Running DynamicMachine Words: 998002, numbers: 6816 0.56 s Running FastDynamicMachine Words: 998002, numbers: 6816 0.29 s Running SimpleMachine Words: 998002, numbers: 6816 0.20 s
What's left unexamined
There are still several implementations of finite state machines left uncovered (I recommend http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml and http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), generators that build machines from descriptions, the Meta State Machine library from Boost version 1.44.0, as well as formal descriptions of finite state machines. The curious reader can familiarize himself with all of the above on his own.
The result of the machine's operation is determined by its final state.
There are various options for specifying a finite state machine. For example, a state machine can be specified using five parameters: , where:
The machine starts working in state q 0, reading one character at a time from the input string. The read symbol transfers the machine to a new state from Q in accordance with the transition function. If, upon completion of reading the input word (chain of symbols), the automaton is in one of the accepting states, then the word is “accepted” by the automaton. In this case, it is said to belong to the language of the given automaton. Otherwise the word is "rejected".
State machines are widely used in practice, such as in parsers, lexical analyzers, and model-based software testing.
Other ways of describing
- State diagram ( or sometimes transition graph) - graphical representation of a set of states and transition functions. It is a loaded unidirectional graph, the vertices of which are the states of the spacecraft, the edges are transitions from one state to another, and the symbols at which this transition occurs. If the transition from state q1 to q2 can be carried out upon the appearance of one of several symbols, then all of them must be inscribed above the arc of the diagram (branch of the graph).
- Transition table- tabular representation of the function δ. Typically, in such a table, each row corresponds to one state, and each column corresponds to one valid input character. The cell at the intersection of the row and column records the action that the machine must perform if, in a situation where it was in a given state, it received a given symbol at the input.
Determinism
Finite machines are divided into deterministic and non-deterministic.
Deterministic finite state machine
- A deterministic finite automaton (DFA) is an automaton in which for each sequence of input symbols there is only one state into which the automaton can go from the current one.
- A non-deterministic finite automaton (NFA) is a generalization of a deterministic one. Non-determinism of automata is achieved in two ways:
| There are transitions marked with an empty chain ε | Several transitions, marked with the same symbol, emerge from one state |
|---|---|
If we consider the case when the machine is specified as follows: , where:
Then the third sign of nondeterminism appears - the presence of several initial (starting) states of the automaton.
There is a theorem that states that “Any non-deterministic finite automaton can be converted into a deterministic one so that their languages coincide” (such automata are called equivalent). However, since the number of states in an equivalent DFA in the worst case grows exponentially with the number of states of the original DFA, in practice such determinization is not always possible. In addition, finite state machines with outputs are generally not determinizable.
Due to the last two remarks, despite the greater complexity of non-deterministic finite automata, NFAs are predominantly used for tasks related to text processing.
Automata and regular languages
For an automaton, one can define a language (a set of words) in the alphabet Σ that it represents- these are the names of words, when entered, the machine goes from the initial state to one of the states of the set F.
Specialized programming languages
- Sequential Function Chart (SFC) language is a graphical programming language widely used for programming industrial logic controllers (PLCs).
In SFC, a program is described as a schematic sequence of steps connected by transitions.
Model development using finite state machines
Finite machines make it possible to build models of parallel processing systems; however, in order to change the number of parallel processes in such a model, it is necessary to make significant changes to the model itself. In addition, an attempt to develop a complex model on a finite state machine will lead to a rapid increase in the number of states of the machine, which will ultimately make the development of such a model an extremely tedious task. As noted above, the last problem can be solved by using a non-deterministic automaton.
Notes
See also
- Sequential logic (Sequential logic)
Links
- Theory of automata / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorenz, A. F. Petrenko, V. P. Chapenko // Probability theory. Mathematical statistics. Theoretical cybernetics. - M.: VINITI, 1976. - T. 13. - P. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
- Application of finite state machines to solve automation problems
- An example of a finite state machine implementation in Python for the Django framework
Wikimedia Foundation. 2010.
- Keynes, John Maynard
- State diagram (automaton theory)
See what a “Finite State Machine” is in other dictionaries:
state machine- CA Computational model describing an automaton with a finite number of states. CAs are widely used in programming, for example, in lexical analyzers of compilers. finite state machine Sequence specification... ...
State machine - mathematical model devices with finite memory. A state machine processes a plurality of discrete input signals into a plurality of output signals. There are synchronous and asynchronous finite state machines. In English: Finite state machine See... Financial Dictionary
state machine- baigtinis automatas statusas T sritis automatika atitikmenys: engl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. finite state machine, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas
FINITE STATE MACHINE- an automaton, which has many states, as well as many input and output signals, are finite. K. a. may be a technical model. devices (computer, relay device) or biol. systems (idealized animal nervous system). Important... ... Big Encyclopedic Polytechnic Dictionary
modular state machine