What is the post about?
This material presents a brief description of the problem in the theory of digital automata and explains one of the ways to solve this problem, which was found when trying to automate the process of building digital automata.
Introduction
Automatic machine is a system of mechanisms, devices, in which the processes of receiving, converting, transferring energy, materials, information are fully automated.
The term "automaton" is mainly used in two aspects:
technical;
mathematical.
In the mathematical approach, an automaton is understood as a mathematical model, which must have inputs, internal states and outputs. The details of the structure of the device are not considered or considered.
In the technical approach, an automaton is understood as a completely real device, for example, a telephone machine, a vending machine, etc. In this case, of course, the details of the internal structure of the device are known.
From the point of view of signals, a digital automaton (DA) is a system that can receive input signals, under their influence, move from one state to another, save it until the next input signal arrives, and issue output signals.
This paper deals with digital signals and binary logic based on logical elements.
. , , , , .
— .
(). , , , , . .
-- . :
1) , .
2) -- .
3) . :
, S -- , ceil -- , .
4) . . , .
5) -.
6) . -, .
7) .
8) .
-- , .
. . (, , ). . -- . <<>>, <<>>. .
(M) (S).
:
(V) (S) (C), :
(A) :
, . .
.
6720. .
( ), 0( ) 1( ).
:
: 5
: ceil(log2(5)) = 3
: 1
:
(V) X(X<S!) . -- . c S! .
, -- 0 1 .
For complex automata, where enumeration takes a lot of time, an effective solution would be to apply a genetic algorithm, it does not necessarily find the best outcome, but it will allow you to quickly find a solution close to it.