Finite state machines for dummies. Finite state machines: converters and recognizers. Automata and regular languages

Lecture 5.

Deterministic Finite State Machines

Discrete-deterministic models ( F-schemes)

Basic relationships. Let us consider the features of the discrete-deterministic approach using the example of using automata theory as a mathematical apparatus. The system is represented in the form of an automaton as a device with input and output signals, processing discrete information and changing its internal states only at acceptable times. State machine is an automaton whose sets of internal states, input and output signals are finite sets.

Abstractly, a finite automata can be represented as a mathematical circuit ( F-diagram), characterized by six elements: a finite set X input signals (input alphabet); finite set Y output signals (output alphabet); finite set Z internal states (internal alphabet or alphabet of states); initial state z 0 , z 0 Î Z; transition function j( z, x); output function y( z, x). Automaton specified F-scheme: F = á Z, X, Y, y, j, z 0 ñ, operates in discrete time, the moments of which are clock cycles, each of which corresponds to constant values of the input and output signals and internal states. Let us denote the state, as well as the input and output signals corresponding to t-th beat at t= 0, 1, 2, …, through z(t), x(t), y(t). Moreover, according to the condition z(0) = z 0 , a z(t)Î Z, x(t)Î X, y(t)Î Y.

Example. The simplest automaton of lion behavior.

Input alphabet: "antelope", "hunter".

Internal states: “full”, “hungry”.

Output alphabet: "eat", "sleep", "run away"

Transition table:

An abstract state machine has one input and one output channel. At every moment t= 0, 1, 2, … discrete time F- the machine is in a certain state z(t) from many Z states of the machine, and at the initial moment of time t= 0 it is always in the initial state z(0) = z 0 . At the moment t, being able z(t), the machine is capable of receiving a signal on the input channel x(t)Î X and output a signal on the output channel y(t) = y[ z(t), x(t)], passing into state z( t+1) = j[ z(t), x(t)], z(t)Î Z, y(t)Î Y. An abstract finite machine implements some mapping of a set of words of the input alphabet X for many words of the output alphabet Y. In other words, if the input of a finite state machine set to the initial state z 0 , supply letters of the input alphabet in some sequence x(0), x(1), x(2), ..., i.e. input word, then the letters of the output alphabet will appear sequentially at the output of the machine y(0), y(1), y(2), ..., forming the output word.

Thus, the operation of the finite state machine occurs according to the following scheme: in each t th cycle to the input of the machine, which is in the state z(t), some signal is given x(t), to which it reacts with a transition ( t+1)-th cycle to a new state z(t+1) and producing some output signal. The above can be described by the following equations: for F-automaton of the first kind, also called automatic miles,

z(t+1) = j[ z(t), x(t)], t= 0, 1, 2, …; (2.15)

y(t) = y[ z(t), x(t)], t= 0, 1, 2, …; (2.16)

For F-automatic machine of the second type

z(t+1) = j[ z(t), x(t)], t= 0, 1, 2, …; (2.17)

y(t) = y[ z(t), x(t – 1)], t= 1, 2, 3,…. (2.18)

Automaton of the second kind, for which

y(t) = y[ z(t)], t= 0, 1, 2, …, (2.19)

those. the output function does not depend on the input variable x(t), called Moore machine gun.

Thus, equations (2.15)-(2.19), completely defining
F-automaton are a special case of equations (2.3) and (2.4), when
system S– deterministic and its only input receives a discrete signal X.

Based on the number of states, finite state machines are distinguished with and without memory. Automata with memory have more than one state, while automata without memory (combination or logical circuits) have only one state. Moreover, according to (2.16), the operation of the combinational circuit is that it assigns each input signal x(t) defined output signal y(t), i.e. implements a logical function of the form

y(t) = y[ x(t)], t= 0, 1, 2, … .

This function is called Boolean if the alphabet X And Y, to which the signal values belong x And y, consist of two letters.

Based on the nature of discrete time counting, finite state machines are divided into synchronous and asynchronous. In synchronous F In automatic machines, the moments of time at which the machine “reads” the input signals are determined by forced synchronizing signals. After the next synchronizing signal, taking into account the “read” and in accordance with equations (2.15)-(2.19), a transition to a new state occurs and a signal is issued at the output, after which the machine can perceive the next value of the input signal. Thus, the response of the machine to each value of the input signal ends in one clock cycle, the duration of which is determined by the interval between adjacent synchronizing signals. Asynchronous F-the machine reads the input signal continuously and therefore reacts to a sufficiently long input signal of constant value x, it can, as follows from (2.15)-(2.19), change its state several times, producing the corresponding number of output signals, until it becomes stable, which can no longer be changed by a given input signal.

Possible applications F-schemes. To set the end F-automaton, it is necessary to describe all elements of the set F= <Z, X, Y, y, j, z 0 >, i.e. input, internal and output alphabets, as well as functions of transitions and outputs, and among the many states it is necessary to select the state z 0 in which the machine is in the state t= 0. There are several ways to specify work F-automata, but the most commonly used are tabular, graphical and matrix ones.

In the tabular method, tables of transitions and outputs are specified, the rows of which correspond to the input signals of the machine, and the columns - its states. The first column on the left corresponds to the initial state z 0 . At the intersection i th line and k the th column of the transition table contains the corresponding value j( z k, x i) transition functions, and in the output table - the corresponding value y( zk,x i) output functions. For F-Moore's automaton both tables can be combined.

Job Description F-A Mealy automaton with tables of transitions j and outputs y is illustrated in Table. 2.1, and the description F-Moore automaton – transition table (Table 2.2).

Table 2.1



Transitions
	j( z 0 , x 1)	j( z 1 , x 1)	j( z k,x 1)
	j( z 0 , x 2)	j( z 1 , x 2)	j( z k,x 2)

	j( z 0 , x i)	j( z 1 , x i)	j( z k,x i)
Exits
	y( z 0 , x 1)	y( z 1 , x 1)	y( z k, x 1)
	y( z 0 , x 2)	y( z 1 , x 2)	y( z k, x 2)

	y( z 0 , x i)	y( z 1 , x i)	y( z k, x i)

Table 2.2




j( z 0 , x 1)	j( z 1 , x 1)	j( z k, x 1)
j( z 0 , x 2)	j( z 1 , x 2)	j( z k, x 2)

j( z 0 , x i)	j( z 1 , x i)	j( z k, x i)

Examples of the tabular method of assignment F-automatic Mili F 1 are given in table. 2.3, and for F-Moore machine gun F 2 – in table. 2.4.

Table 2.3



Transitions


Exits

Table 2.4

When specifying a finite automaton graphically, the concept of a directed graph is used. The graph of an automaton is a set of vertices corresponding to various states of the automaton and connecting the vertices of the graph arcs corresponding to certain transitions of the automaton. If the input signal x k causes a state transition z i in a state z j, then on the automaton graph there is an arc connecting the vertex z i with top z j, denoted x k. In order to specify the output function, the arcs of the graph must be marked with the corresponding output signals. For Mili machines this marking is done as follows: if the input signal x k affects the state z i, then we get an arc emanating from z i and marked x k; this arc is additionally marked with an output signal y= y( z i, x k). For a Moore machine, a similar graph layout is as follows: if the input signal x k, acting on some state of the automaton, causes a transition to the state z j, then the arc directed to z i and marked x k, additionally celebrated as a day off
signal y= y( z j, x k).

In Fig. 2.4. A, b are given by the previously specified tables F-Mili machines F 1 and Moore F 2 respectively.

Rice. 2.4. Graphs of automata a – Mealy and b – Moore

With a matrix specification of a finite automaton, the connection matrix of the automaton is square WITH=||Withij||, rows correspond to initial states, and columns correspond to transition states. Element Withij = x k/y s, standing at the intersection
i th line and j the th column, in the case of a Mili machine corresponds to the input signal x k, causing a transition from the state z i in a state z j, and the output signal y s, issued during this transition. For machine Mili F 1, discussed above, the connection matrix has the form:

x 2 /y 1 – x 1 /y 1

C 1 = x 1 /y 1 – x 2 /y 2 .

x 1 /y 2 x 2 /y 1 –

For F-Moore automaton element Withij equal to the set of input signals at the transition ( z i ,z j), and the output is described by the vector of outputs

= y( z k) ,

i-th component of which is the output signal indicating the state z i.

For the above F-Moore machine gun F2 connection matrices and output vector have the form:

– x 1 – x 2 –at 1

– x 2 – – x 1 at 1

C 2 = – x 2 – – x 1 ; = y 3

x 2 – x 1 – –at 2

x 2 – x 1 – –at 3

For deterministic automata, the condition of unambiguous transitions is satisfied: an automaton that is in a certain state cannot transition to more than one state under the influence of any input signal. In relation to the graphical method of assignment F-of an automaton, this means that in the graph of an automaton, two or more edges marked by the same input signal cannot exit from any vertex. And in the matrix of connections of the machine WITH In each line, any input signal should not appear more than once.

Thus, the concept in the discrete-deterministic approach to studying the properties of objects using models is a mathematical abstraction, convenient for describing a wide class of processes of functioning of real objects in automated control systems. By using F- automaton, it is possible to describe objects that are characterized by the presence of discrete states, and the discrete nature of work in time - these are computer elements and nodes, control, regulation and control devices, time and spatial switching systems in information exchange technology, etc.

Example of modeling using finite state machines

An example of constructing a finite state machine (processor)

for recognizing and processing the recording of real numbers

At the input of the machine: a character string representing an unsigned real number.

At the output of the machine: a pair of integers: mantissa and exponent, or an error message if the number is written incorrectly.

Example.

1. 38.71 E - 42 → (3871, -44);

2. .9 E 21 → (9, 20);

3. 4.5.6 .9→ Error;

4. 3. E 4 → (3, 4);

5. 12 → (12, 0);

6. 1.2 → (12, -1).

In this example, we will show a sample for solving the problem of constructing a finite recognition machine and a processing processor. Let's break this process down into several stages.

1.Write down one or more examples characteristic chains based on which:

a) determine the input alphabet;

b) sign under the symbols of the state chains, simulating the operation of the machine;

c) write down verbal descriptions of states.

a) Input alphabetA=(t E. + -); (where c is the number 0..9)

b) Examples.

Input chain: 3 8 . 7 1 E – 4 2

Machine states: Ø 1 1 2 3 3 4 5 6 6

Input chain: . 9 E 2 1.

Machine states: Ø7 3 4 6 6.

c) Ø initial state; waiting for the mantissa digit or dot.

1 – the digit of the first part of the mantissa is read; waiting for another number or dot, or symbol E.

2 – point read; waiting for a fractional digit or symbol E.

3 – the digit of the fractional part of the mantissa is read; waiting for another number or symbol E.

4 – symbol E read; waiting for +, -, or exponent digits.

5 – the order sign is read; waiting for the order number.

6 – the order number is read; waiting for another number.

7 – the dot is read as the 1st character of the input chain; waiting for the required digit of the fractional part of the mantissa.

Er- error status.

2. Construct a circuit and transition table of a finite state machine.

All transitions not marked with arrows lead to the Er error state.

					Admissibility








Er

Here, all empty cells correspond to a transition to the Er error state.

3.Bring the resulting automaton to its minimal form.

There are special mathematical methods that allow optimizing finite state machines, that is, finding redundant states of the machine. There are algorithms for reducing the automaton to a minimal form. From the results of applying such an algorithm, the equivalence of states 2 ~ 3 follows.

It is easy to verify that all states are reachable by looking at the transition diagram of the machine. Thus, to obtain a minimal reduced automaton, factorization should be carried out by combining states 2 and 3.

For convenience of further description, we rename the states as follows:

Below is the new diagram and state machine transition table.

New transition table:








Er

Processor procedure call table:

	2 a		7 a
	2 b	4 a	3 a
	3 b	4 b
	6 a			5 a
	6 b
	6 c
	3 c
Er

4. Build a processor that processes the end-of-line character.

(In the table, all empty cells correspond to a call to the “NO” procedure, which rejects the input chain). The Yes procedure ends the operation of the machine, accepting the input chain and producing the result of its processing.

5. Supplement processor transitions with procedure names.

For convenience, in this case, the name of the procedure is formed from the number of the state into which the machine goes, supplemented by a serial letter of the Latin alphabet (see also the diagram in the figure).

Note: if the processor must issue an error message, then you should enter designations for the procedures for processing each type of error, filling in all the empty cells of the table with them.

6. Enter the necessary registers - variables needed by the machine to obtain the result.

Number – register of the significant part of a number (integer).

Order– order register (integer).

Counter– register of the counter of digits after (integer).

Sign- (±1) – order sign.

7. Describe the procedures called in accordance with the table and processing the values of processor registers.

2a: Number:= c

2c: Number := 10 * Number+ c

3a: Counter := 0

3c: Counter := Counter + 1

Number := 10 * Number+ c

3c: Number:= c; Counter =: 1

4a: Counter =: 0

5a: Sign:= (+1 if a=’+’ or -1 if a=’-‘) (here a is the input symbol.)

6a: Sign := +1

Order:= c

6c: Order:= c

6s: Order := 10 * Order+ c

Yes1: Order := 0

Yes2: Order:= -Counter

Yes3: Order := Sign * Order - Counter

Here the symbol Æ denotes the absence of any action - an empty procedure. In cases where an integer register is assigned a character (for example: Counter=ts), we mean the implicit conversion of a digit symbol into the number it denotes.

7.Check the operation of the machine (procedure) on one or more chains so that each transition of the machine is carried out at least once.

As examples, consider the operation of the machine in processing the following three input chains. The expected value of the Number and Order registers at the processor output is indicated in parentheses.

a) 67.89E-12┤ (6789, -14)

b) 2E3┤ (2,3)

c) .89┤ (3,-1)

Input symbol	Transition to state, procedure	Register values
Input symbol	Transition to state, procedure	Number	Order	Counter	Sign
	1 (initial)
		6
		67
		67		0
		*678*		1
		*6789*		2

					-1


		*6789*	*-14*
	1 (initial)
		2
				0
			3		+1
		2	3
	1 (initial)

		8		1
		89
		89	-2

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 machine is in one of the accepting states, then the word is “accepted” by the machine. 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 symbol. 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

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 of a device 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- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. English-Russian dictionary of electrical engineering and power engineering, Moscow, 1999] Topics of electrical engineering, basic concepts EN finite modular automaton ... Technical Translator's Guide

accessibility state machine- (ITU T Y.1711). Topics: telecommunications, basic concepts EN availability state machineASM... Technical Translator's Guide

State machine with memory- A finite state machine with memory is a mathematical model of a device whose behavior depends on both input conditions and the previous state. To describe a finite automaton with memory, the languages of operator schemes, regular... ... Wikipedia are used

deterministic finite state machine- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. English-Russian dictionary of electrical engineering and power engineering, Moscow, 1999] Topics of electrical engineering, basic concepts EN finite deterministic automaton ... Technical Translator's Guide

Moore machine- (automaton of the second kind) in the theory of calculations, a finite automaton, the output value of the signal in which depends only on the current state of the given automaton, and does not directly depend, unlike the Mealy automaton, on the input values. Moore's automaton is named... Wikipedia

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:

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 symbol. 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.

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

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

Notes

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:

accessibility state machine- (ITU T Y.1711). Topics: telecommunications, basic concepts EN availability state machineASM... Technical Translator's Guide

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 the help of them, 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 state assumes that we are currently considering a 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

- Lower 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 insignificant)

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 transition template parameters, 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 built 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.

Finite state machine theory

Automata theory underlies the theory of compiler construction. A finite state machine is one of the basic concepts. By automaton we do not mean a really existing technical device, although such a device can be built, but a certain mathematical model, the properties and behavior of which can be imitated using a program on a computer. A finite automaton is the simplest model of automata theory and, as a rule, serves as a control device for all other types of automata. The finite state machine has a number of properties:

· A state machine can solve a number of lightweight compilation problems. The lexical block is almost always built on the basis of a finite state machine.

· The operation of the finite state machine is characterized by high performance.

· State machine modeling requires a fixed amount of memory, which simplifies memory management.

· there are a number of theorems and algorithms that allow you to construct and simplify finite state machines.

There are several different definitions of a finite state machine in the literature. However, what they have in common is that a finite state machine models a computing device with a fixed amount of memory that reads sequences of input symbols belonging to some input set. The fundamental differences in definitions are related to what the machine does at the output. The output of the machine can be an indication of whether a given input chain is “acceptable” or not. “Acceptable” is a correctly constructed or syntactically correct chain. For example, a chain that is supposed to represent a numeric constant is considered incorrectly constructed if it contains two decimal points.

Definition: A finite state machine is a formal system that is defined using the following objects:

· finite set of input symbols;

· finite set of states;

· a transition function that assigns each pair (current state, input symbol) a new state;

· initial state;

· a subset of states identified as permissive or final.

Example. Let's analyze the operation of a controller that checks whether the number of ones is even or odd in an arbitrary chain consisting of zeros and ones. Let us assume that the corresponding finite automaton must “accept” all chains containing an odd number of ones and “reject” chains with an even number. Let's call this machine a “parity controller”. We believe that symbols other than 0 and 1 cannot be submitted to the input of the machine. So, the input alphabet of the controller is the set (0, 1) . We believe that at a particular moment in time the finite automaton deals with only one input symbol, and stores information about the previous symbols of the input chain using a finite set of states. We will consider the set (even, odd) as a set of states; one of these states must be chosen as the initial one. Let it be the state (even), since at the first step the number of ones read is zero, and zero is an even number. When reading the next input symbol, the state of the machine either changes or remains the same, and its new state depends on the input symbol and the current state. This change of state is called a transition.

The operation of the machine can be described mathematically by a transition function of the form d(Scurrent, x) = Snew. Otherwise it can be written as follows:

d(even, 0) = even. d(even, 1) = odd.

d(odd, 0) = odd. d(odd, 1) = even.

The controller has a single accepting state, ODD, and EVEN is a “rejecting” state. Let us reflect the sequence of transitions of the machine when chain 1101 is supplied to its input.

EVEN ® ODD ® EVEN ® EVEN ® ODD

The transition table of such an automaton has the form:


even	even	odd
odd	odd	even

Definition. A finite state machine is a formal system

S = ( A, Q, d, l, V ),

whose objects are the following:

* A is a finite set of input symbols (set

terminals);

* Q - finite set of internal states of the automaton

(set of non-terminals);

* V - finite set of output symbols (output alphabet);

* d - transition function, which is characterized by A ´ Q ® Q;

* l - output function that determines the display of the view.

Finite state machines for dummies. Finite state machines: converters and recognizers. Automata and regular languages

Other ways of describing

Determinism

Automata and regular languages

Specialized programming languages

Model development using finite state machines

Notes

See also

Links

See what a “Finite State Machine” is in other dictionaries:

Other ways of describing

Determinism

Automata and regular languages

Specialized programming languages

Model development using finite state machines

Notes

See also

Links

See what a “Finite State Machine” is in other dictionaries:

Introduction

Practical application of automatic machines

Automaton using switch instructions

Runtime Interpretation

Interpretation of execution time. Speed optimization

Boost Statechart

Performance

What's left unexamined

Finite state machines for dummies. Finite state machines: converters and recognizers. Automata and regular languages

Other ways of describing

Determinism

Automata and regular languages

Specialized programming languages

Model development using finite state machines

Notes

See also

Links

See what a “Finite State Machine” is in other dictionaries:

Other ways of describing

Determinism

Automata and regular languages

Specialized programming languages

Model development using finite state machines

Notes

See also

Links

See what a “Finite State Machine” is in other dictionaries:

Introduction

Practical application of automatic machines

Automaton using switch instructions

Runtime Interpretation

Interpretation of execution time. Speed ​​optimization

Boost Statechart

Performance

What's left unexamined

Interpretation of execution time. Speed optimization