Basic definitions of n A finite automaton is a system M =(А, B, S, y) in which n n n А = (а 1, . . . , am) is a finite input alphabet, B =(b 1, . . . , bk ) - finite output alphabet, S =(s 1, . . . , sn) - finite state alphabet, : A S S - transition function, y: A S B - output function. n If in the automaton M one state is selected, called the initial state (usually it will be considered that this is s 1), then the resulting automaton is called initial and is denoted by (M, s 1). n There are two ways to define an automaton: Automaton table, transition diagram
Automaton table n 1) 2) 3) 4) Example: set the automaton for reading the word "001" if the characters "0" and "1" are input. Input alphabet A=(0, 1) Output alphabet A=(Y, N) State alphabet S=(s 0 "" , s 1 " 0" , s 2 " 00" s 3 "001" ) Automatic table in two ways. 1) Rows are the states of the automaton. The columns are the input symbols. At the intersection of rows and columns, functions are indicated, y. 2) S, A, y are given by columns. Exercise 25 Build an automaton to search for the word CAKADU SA 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1 , N S 0, N S In y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3
Transition diagram n An oriented multigraph, called a transition diagram, is a multigraph, transition or graph corresponding to states. If (Si, aj)=Sk, y(Si, aj)=bl, then from the vertex Si to the vertex Sk there is an arc on which is written (aj, bl) n At each vertex si, the correctness conditions are: 0 1 S 0 "" S 1, N S 0, N S 1 "0" n Vertices, y S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1, N S 0, N 1, N fulfilled 1) for any input letter aj has an arc outgoing from si, on which aj is written (completeness condition); 2) any letter aj occurs only on one edge outgoing from si (consistency or determinism condition) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3
Automata and input words n For a given automaton M, its functions are M and y. M can be defined not only on the set A of all input letters, but also on the set A* of all input words. n For any input word = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2. . . ajk) = y((… (si, aj 1), aj 2), . . . , ajk-1), ajk).
Example: Automata and input words Example: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2 , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) \u003d N, y S 2, N S 3, Y S 3 "001" S 1, N S 0, N
Automaton mapping n Let us fix an initial state S 0 in M and for each input word = a 1 a 2. . . ak we assign a word in the output alphabet: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1. . . ak). (3 a) n This correspondence, which maps input words to output words, is called an automaton mapping n If the result of applying an operator to a word is an output word, then this will be denoted accordingly by M() = .
Example: Automatic Mapping Let's assign the input word = 0101 to the word in the output alphabet: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0)= N, y 0 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y 1 S 3 "001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN
Automaton display properties 1) words and = M() have the same length: | | = | | (property of preservation of length); 2) if = 1 2 and M(1 2) = 1 2, where | 1| = | 1|, then M(1) = 1; in other words, the image of a segment of length i is equal to the segment of the image of the same length.
Types of automata n The general model of a finite automaton (S-finite), which was considered earlier, is called a Mealy automaton. n An automaton is called autonomous if its input alphabet consists of one letter: A=(a). All input words of the autonomous automaton have the form aa. . . a. n A finite automaton is called a Moore automaton if its output function depends only on states, i.e., for any s, ai, aj y(s, ai) = y(s, aj). The output function of the Moore automaton is naturally one-argument; it is usually denoted by a letter and is called the marks function. In the graph of the Moore automaton, the output is written not on the edges, but at the top.
Moore automata n Theorem: For any Mealy automaton there exists an equivalent Moore automaton. n When studying the possibilities of automata, it is sufficient to use Moore automata. This is convenient because the Moore automaton can be viewed as an automaton without outputs, the states of which are labeled in various ways.
An example of an autonomous automaton SA a S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 S 8 S 9, 0 S 9, 1 S S S S S A=(a), B=(0, 1, 2), S=(S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S9)
Indistinguishable States n Let M and T be two automata with the same input and output alphabets. A state s of an automaton M and a state r of an automaton T are said to be indistinguishable if for any input word M(s,) = T(r,). n The automata M and T are called indistinguishable if for any state s of the automaton M there is a state r of the automaton T that is indistinguishable from it and, conversely, for any r from T there is an indistinguishable state s from M. n Indistinguishable states are called equivalent
Minimal automaton n The transition from an automaton M to an equivalent automaton is called an equivalent transformation of an automaton M. n One can pose various problems of finding automata that are equivalent to a given automaton and have given properties. The most studied among such problems is the problem of minimizing the number of states of an automaton: among automata equivalent to M, find the automaton with the smallest number of states - the minimal automaton.
Aspects of the “work” of automata n Two main aspects of the “work” of automata can be distinguished: 1) automata recognize input words, i.e. answer the question of whether the input word belongs to a given set (these are recognizer automata); 2) automata transform input words into output words, i.e., they implement automaton mappings (transformer automata).
TA in the framework of metamathematics n The subject of the theory of algorithms and formal systems in the framework of metamathematics - what objects and actions on them should be considered precisely defined, what properties and capabilities combinations of elementary actions have, what can and cannot be done with their help. n The main application of the theory of algorithms is the proof of the impossibility of an algorithmic (ie, exact and unambiguous) solution of certain mathematical problems.
Algorithm n An algorithm is a prescription that uniquely specifies the process of transforming the initial data to the required result n The transformation process itself consists of elementary discrete steps, the application of which a finite number of times leads to the result
Basic types of algorithms n The theory of algorithms is a metatheory that studies various (qualitative and quantitative) properties of algorithms. n For the study of qualitative properties, 3 main types of algorithms are defined: 1) Recursive functions 2) Turing machine 3) Canonical Post systems and normal Markov algorithms.
The simplest recursive functions n S 1(x) = x+1 - the function depends on one variable x, and is equal to x+1. n On(x 1…xn) =0 - function depending on n variables and always equal to 0. n Imn(x 1…xn) = xm - function depending on n variables and always equal to the value of variable xm
Primitive recursion n The function f(x 1…xn+1) is obtained by the primitive recursion algorithm from the functions g(x 1…xn) and h(x 1…xn+2) if f(x 1, …xn, 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), where z=f(x 1, …xn, y) (2) Function f is called primitive recursive , if it can be obtained from the simplest functions S 1, On, Imn by a finite number of superposition and primitive recursion operations.
Example n To prove that a function is primitive recursive: 1) According to equations (1) and (2), explicitly define the functions g() and h(). 2) Show that g() and h() are the simplest functions S 1, On, Imn, or primitive recursive functions proven earlier. Exercise 26: Prove that the function f(x, y) = x+y is primitive recursive Church's thesis: The class of algorithmically computable numerical functions coincides with the class of all recursive functions.
Turing machine n Turing machine contains: n 1) External memory - a tape of n cells. Each i-th cell is in the state ai. The alphabet of states is set. The tape can be endless in both directions. Empty states are omitted. n 2) The internal memory of the machine - the device is currently in the state qi. The alphabet of the internal state is given. Initial state q 1, final q 0 or qz. n 3) Pointer - points to the current cell and moves along the tape. n 4) Control device - reads the character of the cell pointed to by the pointer. In accordance with the program, changes the state of the cell and moves the pointer.
The state and program MT n The state of the Turing machine is called the word n n n n a 1…ak-1 qi ak…ar , formed by inserting the symbol of the internal state in front of the monitored cell. The Turing machine program is a set of commands that can be executed by the machine qi aj qi' aj' D, where qi is the internal state of the machine aj is the state of the monitored cell qi' is the new state of the machine aj' is a new character written to the monitored cell D = ( L, R, E) - characters symbolizing the shift of the pointer by one cell to the left, to the right and the absence of a shift, respectively.
Example MT Exercise 27: Find the final state of the Turing machine Initial alphabet: A = (0, 1) Internal state alphabet: Q = (q 0, q 1, q 2) Program: ( 1) q 10 q 20 R, 2) q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Initial word: q 111
Example MT Control 28 Find the final state of the Turing machine Initial alphabet: A \u003d (0, 1, ) Alphabet of the internal state: Q \u003d (q 0, q 1, q 2, q 3) Program: ( 1) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L) A) Initial word: q 111 1 B) Initial word: q 11 111
Turing's thesis Turing's thesis: for each algorithm A, a Turing machine can be built that, given the same initial data, gives the same results as algorithm A. n If 1 q 1 2 1 qz 2, then we will say that the machine T processes the word 1 2 into the word 1 2, and denote it T(1 2) = 1 2. n The notation T() is the designation of the machine T with initial values.
Normal Markov Algorithms n Normal Markov Algorithms (NAM) transform words of finite length into each other using substitution. n Task NAM Substitution Alphabet u v Final substitution u v n Control 29 A normal Markov algorithm is specified: Alphabet is the alphabet of the Russian language. Substitution scheme (I U, L U, S M, V B, R T, T R, O X, N A) n Initial word SLON. n Find end word.
Estimating the complexity of algorithms n Suppose that the functions f(n) and g(n) measure the performance of two algorithms, they are usually called time complexity functions. We will say that the order of growth of the function f(n) is not greater than that of g(n) if there exists a positive constant C such that | f(n) |
Efficiency of algorithms A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1024 s 100 ms 30 s 20.4 ms 0.28 h 4*1017 centuries 0.56 h 11.6 days 10176 centuries 1000 ms 0.83 h 1 ms
Theory of Algorithms n Theory of Algorithms - classifies problems by complexity. In this case, only recognition tasks are classified. n A recognition task is a task that answers the question: does the input data have some property. In our case: the input data is a graph, a property - is the graph Hamiltonian?
Classes P and NP n Complexity class P: there is an algorithm A that solves the problem in polynomial time. n Complexity class NP - there is an algorithm A that checks the proposed solution in polynomial time. n The Hamiltonian cycle problem is to find out whether a given graph G has a Hamiltonian cycle belongs to the NP-class.
Examples of NP problems n Boolean satisfiability problem: to find out from a given Boolean formula whether there is a set of variables included in it that turns it into 1. n Clique problem: to find out from a given graph whether there are cliques (complete subgraphs) of a given size in it . n The problem of the existence of a Hamiltonian cycle in a graph. n Existence of an integer solution to a system of linear inequalities.
Possibility of solving NP problems by enumeration of n Initially, the solution is not known. Therefore, it is important that any problem related to the NP-class can be solved in exponential time by enumeration of all possible combinations of n, which happens in the algorithm for finding the Hamilton cycle
Relation between Р and NP n Any task from P belongs to NP. n Thus, class NP includes class P. At this time, it is not known whether classes P and NP are the same, but most experts believe that they are not.
Ratio of P and NP n If it turns out that P = NP 1) NP tasks will be solved in a reasonable time. 2) There are a number of problems that intentionally use problems of exponential complexity (i.e., assuming that the problem cannot be solved). For example, In cryptography, there is a section on public key encryption, which is almost impossible to decrypt. If suddenly P = NP, then many secrets will cease to be such.
NP-Complete Problems n The most compelling reason to believe that P ≠ NP is the existence of NP-complete problems. n Informally!!!, Problem Q reduces to Problem Q′ if Problem Q can be solved in polynomial time for any input, assuming that the solution of Problem Q′ for some other input is known. For example, the problem of solving a linear equation is reduced to the problem of solving a quadratic equation.
NP-complete problems n An NP-complete problem is a problem from the class NP to which any other problem from the class NP can be reduced. n NP-complete problems form a subset of the "hardest" problems in the NP class. If for any NP-complete problem a polynomial solution algorithm is found, then any other problem from the NP class can be solved in polynomial time. n All listed NP-problems are NP-complete. Including the problem of the Hamilton cycle.
Baranov Viktor Pavlovich Discrete Math. Section 6. State Machinesand formal languages.
Lecture 31 Synthesis task. Elementary cars and you
Lecture 30 DEFINITION AND METHODS OF DESIGNATION OF FINITE AUTOMAT.
SYNTHESIS PROBLEM. ELEMENTARY AUTOMATES
Lecture plan:
1. Definition of a finite automaton.
2. Methods for defining a finite automaton.
- The problem of automata synthesis.
- Elemental machines.
- The problem of the completeness of an automaton basis.
- Canonical method for automaton synthesis.
- State machine definition
SFE do not take into account the fact that real devices operate in time. Compared to the SFE, the finite automaton is a more accurate model of a discrete converter. b information developer. At the same time, the concept of a finite automaton, like any model, is I but with a number of simplifying assumptions.
First, it is assumed that the input and output of the automaton can be in only one of a finite number of different states at any time. If real b If a converter has a continuous input signal, then to describe it using a finite automaton, it is necessary to quantize this signal. In the formal definition of the automaton, the finite set of input and output states of the automaton is called coo t responsibly to the input and output alphabet, and individual states the letters of these alphas and vits.
Second, it is assumed that time changes discretely. The input and output states correspond to a discrete time sequence. b Since the moment of time is uniquely determined by its index, then for the sake of simplicity we will assume that time takes the values 1, 2, ..., ... The time interval is called tact.
The operation of the machine is presented as follows.
The input of the automaton receives signals from the input alphabet, which leads to the appearance of signals at the output from the input alphabet. W a The dependence of the output sequence on the input sequence depends on the internal structure of the automaton. Note that, in contrast to the SFE, which do not have memory, the automaton pre d is a device with memory, i.e., the output of the automaton is determined not only b to the entrance, but also to the backstory. History accounting I is determined by the dependence of the output signal not only on the input, but also on the current state, which we denote.
Let us give a formal definition of an automaton.
state machinename five objects
, (1)
where
input alphabet; one of the possible entry states;
a finite set calledoutput alphabet; element you of this set determine the possible output states;
a finite set calledalphabet of internal states i nii;
transition functionmachine: ; this function assigns a state to each “input-state” pair;
output function machine: ; this function associates each input-state pair with an output value.
The law of the functioning of the automaton: the automaton changes its states in accordance with t function and generates output signals in accordance with the function to the action:
- Ways to define a state machine
1. Tabular assignment method. Since for functions and scope e values and values belong to a finite set, then they are specified using tables.
Example 1 We define the automaton as follows: , . Define the function usingjump tables,and the function using exit tables.
Table 1. Jump table Table 2. Output table
|
Entrance |
State |
||
|
Entrance |
State |
||
If the sequence of signals at the input of the automaton is known, then the tables e moves and exits uniquely determines the output sequence.
2 . Graphical way to set. used transition-output diagram.It is a directed multigraph in which each internal t the vertex corresponds to the early state of the automaton. Transitions of the automaton from state to state are depicted by arrows, on each of which an input symbol is written, in s calling this transition, and the output symbol generated by the automaton.
| | |
Fig.1 Diagram of transitions-outputs
Example 2 It is required to build an automaton that would work as follows a zom: in each cycle, the next binary digits of the terms are received at the input of the automaton, and in the tomato produces the corresponding binary digit of their sum. For two h row terms we have: , .
The automaton is in state 1 if, when adding the previous digits, the and carries carry, and is in state 0 otherwise. Transition-exit diagram and zana in fig. 2.
00|0 11|1 01|0
01|1 10|0
10|1 00|1 11|1
Rice. 2
- The problem of automata synthesis
By analogy with the problem of synthesizing the SFE, one can pose the problem of synthesis for the automatic a comrade There is an unlimited set of basic automata. It is required to assemble an automaton with a predetermined functioning. In this case, the problem of synthesis collides t with certain problems.
Assume that you need to connect the output of the automaton to the input of the automaton. This is possible under the condition that otherwise about swarm machine will not understand the signals coming from the first. This leads to confusing and situations where some connections are not possible.
To overcome this obstacle, the concept of a structural automaton is introduced, in which about all alphabets (input, output, and internal states) are encoded by binary words.
Let be a finite set of elements, and set e set of binary words of length, where. An arbitrary injective mapping will be calledencoding the set in binary words.
Let's encode alphabets for an arbitrary automaton:
Let us denote the encoded input, output, and state of the automaton at the moment of time, respectively. Then the law of operation will be presented in the form
(2)
The automaton obtained after coding is called structural . We assume that the structural automaton has binary inputs, binary outputs, and the internal state of the automaton is given by a binary word of length. On fig. 3 shown abstract automaton and its corresponding structural automaton.
… …
Rice. 3
The transition to a structural automaton provides two important advantages for synthesis. e stva.
1 . Compatibility of inputs and outputs, since binary and n formation. We will not give a general definition of a circuit from structural automata it is similar to SFE.
2 . Let us write relations (2) in “coordinates”:
(3)
From (3) it follows thatthe law of functioning of a structural automaton is given with and Boolean Function Stem.
- Elementary automata
We single out the simplest structural automata and give them a name.
Note first that a functional element that has only one state can be considered as an automaton without memory.
Let's move on to automata with two states. Let the automaton have one binary input and one binary output coinciding with the internal state: :
Rice. four.
To set the automaton shown in Fig. 4, it is enough to specify only the table p e transitions:
Table 3
|
Entrance |
State |
|
Instead of asterisks, you need to put 0 and 1. This can be done in 16 ways, however, not all of them are acceptable. Suppose, for example, that in the first column of table 3 both elements n you are zero. Such an automaton, once in state 0, will no longer exit it, that is, it will work as a functional element. An analysis of similar situations shows that in order to obtain an automaton that is not reducible to an automaton without memory, it is necessary to require about to ensure that each column of Table 3 contains both zero and one. Such tables are ego h e tyre.
Table 4 Table 5
|
Entrance |
State |
|||||
|
Entrance |
State |
|||||
Table 6 Table 7
|
Entrance |
State |
|
|
Entrance |
State |
|
We have only two simplest automata, since 7 is obtained from 4, and 6 from 5 by inversion of internal states.
The automaton given by Table 4 is called delay or -trigger :
that is, this automaton delays the signal by one cycle.
The automaton specified by Table 5 is calledtrigger with counter input or -trigger . The state of the automaton changes to the opposite if the input is 1, and remains unchanged if the input is 0:
Let at the initial time- trigger is in state 0. If in n e which point in time- the trigger is in state 0, this means that an even number of ones has been received at the input of the automaton. If in state 1, then is odd. So arr and zom, - the trigger counts the number of units at the input, but since it has only two states I niya, then counts to two.
When triggers are physically implemented, two outputs are used: direct and inverted (Fig. 5). If we swap them, then- trigger, you get an automaton specified by table 7, and from- trigger automaton specified by Table 6.
Rice. 5.
- The problem of the completeness of an automaton basis
A set of structural automata is called complete (or automaton b a zisom) if it is possible to construct any predetermined structural automaton from them.
The efforts of mathematicians to obtain an analog of Post's theorem for automata are not increased. n chalked up success. In 1964 M.I. Briefly proved the non-existence of an algorithm for determining e system completeness. In this case, variants of the completeness theorem with additional assumptions about the system are of interest. Let's consider the most popular of them.
Theorem. automatic system,containing a full set of PV and -trigger (or -trigger) is complete.
Proof. Consider an arbitrary automaton given by the relation e (2), and describe its scheme of the indicated automata, calledcanonical structure(Fig. 6) .
The scheme consists of two parts.
…
…
…
Rice. 6.
The left half is called the memory part. It consists of triggers, the set of states of which forms the state of the automaton: if at the moment of time
, …,
then it means that the automaton is in the state.
The right half is called the combinational part and represents the SFE. The inputs of this circuit are:
- binary word input signal of the automaton;
- binary word current internal state of the automaton.
Outputs:
- binary word output signal of the automaton, which is implemented t according to formulas (3);
- a binary word that enters the inputs of triggers in memory a current part and controls the memory of the machine.
Let us show that the memory control signals are Boolean functions of the same variables as the output of the automaton, which means that they can be implemented completely with and the FE stem.
At each moment in time, the memory control signals must translate a in tomato from state to state. To do this, you need to change the state of each trigger
, .
The -triggers or -triggers used in the canonical scheme have the following e next property: for any pair of states, there is an input signal, e driving machine from state to state. Let's denote this signal by . For -trigger, since the state in which the -trigger is set is equal to the input signal. For -trigger: when you need to enter n about give 0 to keep the state unchanged; at 1, so that the trigger "flips".
So, or in vector form
Let us express from the law of functioning of the automaton (2). Then
The theorem has been proven.
- Canonical method for automaton synthesis
Let's consider this method on a concrete example.
Example. On the conveyor, along which parts of two types move and, installed in flax machine, whose task is to sort parts in such a way that after passing e passing by the machine, they formed groups. Wrong part machine sta l nods from the assembly line. It is required to build a circuit of such an automaton using a -trigger and elements "AND", "OR", "NOT".
The automaton synthesis is divided into the following stages.
1 . Construction of an abstract automaton.
Input alphabet . Output alphabet , where C part collision, P her pass. The internal states of the automaton reflect its memory of which part of the group it has already formed: . As the group is formed, the automaton moves cyclically through these states without changing the state when an unsuitable part arrives. The transition-output diagram is shown in fig. 7.
| | |
Rice. 7.
2 . Alphabet coding.
One of the possible coding options is given in the following. e blowing tables.
Input Output Status
3 . Construction of the canonical structure of the automaton.
The canonical structure of the automaton being developed is shown in fig. eight.
Rice. eight.
Let us find the dependences of the SFE outputs on the variables, first in tabular form (Table 8), according to k about which we will later construct the formulas
, .
Table 8
These functions are calledpartially defined, since they are not defined at. To represent these functions by formulas, they are extended in such a way as to obtain a simpler form of formulas.
4 . Representation of automaton output functions and memory management functions r mules.
Using the methods of minimizing Boolean functions, we build, if possible, ek about nominal representation of functions, formulas in the basis:
5 . Implementation of the SFE and the final scheme of the automaton (Fig. 9).
Rice. 9.
SFE
SFE
NOT
OR
Combination schemes, although they allow you to implement any fixed dependencies between input and output signals cannot change the nature of their behavior (i.e. data processing sequence) - any such change requires a change in the structure of the circuit, i.e., in fact, a transition to another circuit. It is possible to solve the problem of restructuring the work without changing the structure of the scheme, if we introduce into it memory elements, which would allow fixing and saving the intermediate states of the device - in this case, the output signal will depend not only on the input signal, but also on the state of the circuit. If the number of such elements is finite, then, as mentioned above, the discrete device will be called end machine.
state machinecalled the system
As stated earlier, Y (x,q) specifies the order of transformation of the input symbols and the state of the automaton on the previous cycle into the state on the next one, a Q (x,q) - transformation of input symbols and the state of the automaton at the current cycle into an output symbol. If a q 0 is the initial state of the automaton, and i- measure number, then its work is described by the system:
These ratios are called systems of canonical equations finite automaton. You can use them from q 0 , sequentially find all subsequent states of the automaton and output symbols.
There are two types of machines - initial and non-initial. AT initial automata have a fixed initial state (i.e. they always start from the same state q0). In non-initial automata, any of the set Q; this choice determines the further behavior of the automaton.
The representation of a particular finite automaton is actually reduced to a description of the automaton functions that define it. It follows from system (9.3) that for a finite number of possible internal states, the number of possible values of automaton functions also turns out to be finite. They can be described in various ways, the most common of which is tabular and with the help diagrams.
AT tabular way automaton functions are given by two finite tables, named respectively transition matrix and output matrix. In these tables, the rows are denoted by the letters of the input alphabet, and the columns are denoted by the letters of the internal alphabet (symbols encoding the internal state of the automaton). In the transition matrix at the intersection of the row (xk) and column (qr) the values of the function Y are placed ( q r, x k), a in the matrix of outputs - the values of the function Q (q r , x k).
Baranov Viktor Pavlovich Discrete Math. Section 6. Finite automata and formal languages.
Lecture 31 Synthesis task. Elementary automata
Lecture 30
SYNTHESIS PROBLEM. ELEMENTARY AUTOMATES
Lecture plan:
1. Definition of a finite automaton.
2. Methods for defining a finite automaton.
- The problem of automata synthesis.
- Elemental machines.
- The problem of the completeness of an automaton basis.
- Canonical method for automaton synthesis.
- State machine definition
SFE do not take into account the fact that real devices operate in time. Compared to the SFE, the finite automaton is a more accurate model of a discrete information converter. At the same time, the concept of a finite automaton, like any model, is associated with a number of simplifying assumptions.
First, it is assumed that the input and output of the automaton can be in only one of a finite number of different states at any time. If a real transducer has a continuous input signal, then to describe it using a finite automaton, it is necessary to quantize this signal. In the formal definition of the automaton, the finite set of input and output states of the automaton is called the input and output alphabet, respectively, and individual states are called the letters of these alphabets.
Second, it is assumed that time changes discretely. The input and output states correspond to a discrete time sequence Since the moment of time is uniquely determined by its index, for the sake of simplicity we will assume that the time takes the values 1, 2, ..., ... The time interval is called a tact.
The operation of the machine is presented as follows.
The input of the automaton receives signals from the input alphabet, which leads to the appearance of signals at the output from the input alphabet. The dependence of the output sequence on the input sequence depends on the internal structure of the automaton. Note that, unlike SFE, which do not have memory, the automaton is a device with memory, i.e., the output of the automaton is determined not only by the input, but also by the prehistory. The prehistory is taken into account by the dependence of the output signal not only on the input, but also on the current state, which we denote.
Let us give a formal definition of an automaton.
A state machine is a set of five objects
a finite set called the input alphabet; one of the possible entry states;
a finite set called the output alphabet; the elements of this set define the possible output states;
a finite set called the alphabet of internal states;
automaton transition function: ; this function assigns a state to each “input-state” pair;
function of machine outputs: ; this function associates each input-state pair with an output value.
The law of functioning of the automaton: the automaton changes its states in accordance with the function and generates output signals in accordance with the function:
- Ways to define a state machine
1. Tabular way of setting. Since for functions both the scope and values belong to a finite set, they are specified using tables.
Example 1. Let's define the automaton as follows: , .We define the function using the transition table, and the function using the output table.
Table 1. Jump table Table 2. Output table
|
State |
|||
|
State |
|||
If the sequence of signals at the input of the automaton is known, then the output sequence is uniquely determined by the tables of transitions and outputs.
2. Graphical way of setting. A transition-output diagram is used. It is a directed multigraph in which each internal state of the automaton corresponds to a vertex. Transitions of the automaton from state to state are depicted by arrows, on each of which the input symbol that causes this transition and the output symbol generated by the automaton are written.
Fig.1 Diagram of transitions-outputs
Example 2. It is required to build an automaton that would work as follows: in each cycle, the next binary digits of the terms are received at the input of the automaton, the automaton generates the corresponding binary digit of their sum. For two-digit terms we have: , .
The automaton is in state 1 if a carry occurs during the addition of previous digits, and in state 0 otherwise. The transition-output diagram is shown in fig. 2.
- The problem of automata synthesis
By analogy with the problem of SFE synthesis, one can pose a synthesis problem for automata. There is an unlimited set of basic automata. It is required to assemble an automaton with a predetermined functioning. At the same time, the task of synthesis faces certain problems.
Assume that you need to connect the output of the automaton to the input of the automaton. This is possible under the condition, since otherwise the second automaton will not understand the signals coming from the first one. This leads to a confusing situation where some connections are not possible.
To overcome this obstacle, the concept of a structural automaton is introduced, in which all alphabets (input, output, and internal states) are encoded in binary words.
Let be a finite set of elements, and be a set of binary words of length, where. An arbitrary injective mapping will be called an encoding of a set by binary words.
Let's encode alphabets for an arbitrary automaton:
Let us denote the encoded input, output, and state of the automaton at the moment of time, respectively. Then the law of operation will be presented in the form
The automaton obtained after coding is called a structural automaton. We assume that the structural automaton has binary inputs, binary outputs, and the internal state of the automaton is given by a binary word of length. On fig. Figure 3 shows an abstract automaton and its corresponding structural automaton.
The transition to a structural automaton provides two important advantages for synthesis.
1. Compatibility of inputs and outputs, since binary information is transmitted through them. We will not give a general definition of a circuit from structural automata it is similar to SFE.
2. Let's write relations (2) in "coordinates":
It follows from (3) that the law of functioning of a structural automaton is given by a system of Boolean functions.
- Elementary automata
We single out the simplest structural automata and give them a name.
Note first that a functional element that has only one state can be considered as an automaton without memory.
Let's move on to automata with two states. Let the automaton have one binary input and one binary output coinciding with the internal state: :
To set the automaton shown in Fig. 4, it is enough to set only the transition table:
Table 3
|
State |
||
Instead of asterisks, you need to put 0 and 1. This can be done in 16 ways, however, not all of them are acceptable. Suppose, for example, that in the first column of Table 3 both elements are zeros. Such an automaton, once in state 0, will no longer exit it, that is, it will work as a functional element. An analysis of similar situations shows that in order to obtain an automaton that is not reducible to an automaton without memory, it is necessary to require that both zero and one occur in each column of Table 3. There are only four such tables.
Table 4 Table 5
|
State |
||||||
|
State |
||||||
Table 6 Table 7
|
State |
||
|
State |
||
We have only two simplest automata, since 7 is obtained from 4, and 6 from 5 by inversion of internal states.
The automaton given by Table 4 is called a delay or -trigger:
that is, this automaton delays the signal by one cycle.
The automaton specified by Table 5 is called a trigger with a counting input or a -trigger. The state of the automaton changes to the opposite if the input is 1, and remains unchanged if the input is 0:
Let the -trigger be in state 0 at the initial moment of time. If at some point in time the -trigger is in state 0, then this means that an even number of 1s has been received at the input of the automaton. If in state 1, then is odd. Thus, the -trigger counts the number of units at the input, but since it has only two states, it counts up to two.
In the physical implementation of triggers, two outputs are used: direct and inverse (Fig. 5). If we swap them, then from the -trigger we get the automaton specified by Table 7, and from the -trigger the automaton specified by Table 6.
- The problem of the completeness of an automaton basis
A set of structural automata is called a complete (or automaton basis) if any given structural automaton can be constructed from them.
Efforts by mathematicians to obtain an analogue of Post's theorem for automata were unsuccessful. In 1964 M.I. Briefly proved the non-existence of an algorithm for determining the completeness of a system. In this case, variants of the completeness theorem with additional assumptions about the system are of interest. Let's consider the most popular of them.
Theorem. A system of automata containing a complete set of FEs and a -trigger (or -trigger) is complete.
Proof. Consider an arbitrary automaton given by relations (2) and describe its scheme of the indicated automata, called the canonical structure (Fig. 6).
The scheme consists of two parts.
The left half is called the memory part. It consists of triggers, the set of states of which forms the state of the automaton: if at the moment of time
then it means that the automaton is in the state.
The right half is called the combinational part and represents the SFE. The inputs of this circuit are:
- binary word input signal of the automaton;
- binary word current internal state of the automaton.
- binary word output signal of the automaton, which is implemented according to formulas (3);
- a binary word that enters the inputs of triggers in the storage part and controls the memory of the automaton.
Let us show that the memory control signals are Boolean functions of the same variables as the automaton output, which means that they can be implemented by a complete FE system.
At each moment of time, the memory control signals must transfer the automaton from state to state. To do this, you need to change the state of each trigger
The -triggers or -triggers used in the canonical scheme have the following property: for any pair of states, there is an input signal that transfers the automaton from state to state. Let's denote this signal by . For -trigger, since the state in which the -trigger is set is equal to the input signal. For -trigger: when, 0 must be applied to the input so that the state does not change; at 1, so that the trigger "flips".
So, or in vector form
Let us express from the law of functioning of the automaton (2). Then
The theorem has been proven.
- Canonical method for automaton synthesis
Let's consider this method on a concrete example.
Example. An automatic machine is installed on the conveyor along which parts of two types move, the task of which is to sort the parts in such a way that after passing by the machine they form groups. The machine pushes the unsuitable part off the conveyor. It is required to build a circuit of such an automaton using a -trigger and elements "AND", "OR", "NOT".
The automaton synthesis is divided into the following stages.
1. Construction of an abstract automaton.
Input alphabet . The output alphabet is , where C is the collision of the part, P its skip. The internal states of the automaton reflect its memory of which part of the group it has already formed: . As the group is formed, the automaton moves cyclically through these states without changing the state when an unsuitable part arrives. The transition-output diagram is shown in fig. 7.
2. Coding of alphabets.
One of the possible coding options is shown in the following tables.
Input Output Status
3. Construction of the canonical structure of the automaton.
The canonical structure of the automaton being developed is shown in fig. eight.
Let us find the dependences of the SFE outputs on the variables, first in tabular form (Table 8), according to which we will further construct the formulas
Table 8
These functions are called partially defined because they are not defined at. To represent these functions by formulas, they are extended in such a way as to obtain a simpler form of formulas.
4. Representation of automaton output functions and memory control functions by formulas.
Using the methods of minimizing Boolean functions, we build an economical representation of functions, if possible, by formulas in the basis:
5. Implementation of the SFE and the final scheme of the automaton (Fig. 9).
DEFINITION AND METHODS OF DESIGNATION OF FINITE AUTOMAT. SYNTHESIS PROBLEM. ELEMENTARY AUTOMATES
Automata theory is a section of discrete mathematics that studies models of discrete information converters. Such converters are both real devices (computers, living organisms) and imaginary devices (axiomatic theories, mathematical machines). In essence, a finite state machine can be described as a device M , which has input and output channels, while at each of the discrete time moments, called clock moments, it is in one of the final states.
On the input channel at any time t =1, 2, ... to device M input signals arrive (from some finite set of signals). The law of state change to the next moment of time is set depending on the input signal and the state of the device at the current moment of time. The output signal depends on the state and the input signal at the current time (Fig. 1).
The state machine is a mathematical model of real discrete information processing devices.
state machine called the system A= (X , Q , Y , , ), where X , Q , Y are arbitrary non-empty finite sets, and and - functions, of which:
lots of X ={a 1 , ..., a m ) is called input alphabet , and its elements are input signals , their sequences are in catchphrases ;
lots of Q ={q 1 , ..., q n ) is called many states automaton, and its elements - states ;
lots of Y ={b 1 , ..., b p ) is called output alphabet , its elements are output signals , their sequences are output words ;
function : X Q Q called transition function ;
function :X Q Y called output function .
In this way, (x , q )Q , (x , q )Y for x X , q Q .
An imaginary device is associated with the state machine, which works as follows. It can be in a state from the set Q , receive signals from the set X and issue signals from a set Y .
2. Methods for defining a finite automaton
There are several equivalent ways to define abstract automata, three of which are: tabular , geometric and functional .
2.1. Table assignment of the machine
It follows from the definition of an automaton that it can always be defined by a table with two inputs containing t lines and P columns, where at the intersection of the column q and lines a function values are worth (a i , q j ), (a i , q j ).
|
q a |
q 1 |
q j |
q n |
||
|
a 1 |
(a 1 , q 1), (a 1 , q 1) |
(a 1 , q j ), (a 1 , q j ) |
(a 1 , q n ), (a 1 , q n ) |
||
|
a i |
(a i , q 1), (a i , q 1) |
(a i , q j ), (a i , q j ) |
(a i , q n ), (a i , q n ) |
||
|
a m |
(a m , q 1), (a m , q 1) |
(a m , q j ), (a m , q j ) |
(a m , q n ), (a m , q n ) |
2.2. Defining an automaton by a Moore diagram
Another way to specify a finite state machine is graphical, that is, using a graph. The automaton is represented as a labeled directed graph G(Q , D ) with many vertices Q and many arcs D ={(q j , (a i , q j ))| q j Q , a i X ), while the arc ( q j , (a i , q j )) is labeled with a pair ( a i , (a i , q j )). Thus, with this method, the states of the automaton are depicted by circles, in which the symbols of the states are entered q j (j = 1, …, n ). From each circle is carried out t arrows (directed edges) one-to-one corresponding to the characters of the input alphabet X ={a 1 , ..., a m ). Arrow corresponding to the letter a i X and leaving the circle q j Q , the pair ( a i , (a i , q j )), and this arrow leads to a circle corresponding to (a i , q j ).
The resulting drawing is called automaton graph or, Moore diagram . For not very complex automata, this method is more illustrative than tabular.
