Automated programming. Part 2. State and transition diagram

    In the first article, I gave an example of automatic programming from general to particular, or rather constructive decomposition . The next stage of design, study of the resulting modules. But first, I will show what automata are from a mathematical and practical point of view. Automata is based on a model describing a process that takes place in time, called a state diagram, and it is impossible to imagine automatic programming without this entity. Why this is so discussed in today's article.


    Table of contents.

    Automatic vs automatic


    Experts give a fairly extensive classification of automata: deterministic and non-deterministic, finite and infinite, Miles and Moore, synchronous and asynchronous, etc. However, from the point of view of the user, it’s the same as if a person wanted to decide for himself whether he needed a personal car in the metropolis, and he would be told about the number of cylinders and the injector.

    As a popularizer, I note that from the point of view of use, machines are divided into two related categories:

    • automata as a mathematical abstraction, we also include here the methods of implementing automata.
    • automata as a set of techniques and approaches for designing digital logic devices (circuits and programs), also based on mathematics.

    The relationship between these approaches is easy to illustrate:


    Figure 1. Computer-aided design and computer-aided implementation

    As far as it becomes clear from communication with colleagues, there is a category of formalists who consider machines as:

    • entities whose description should strictly fit into the framework of UML State Diagrams or similar description methods, that is, have a set of nodes defined as separate functions, a set of signals, and a formalized table that defines the relationships between them.
    • the concept of an automatically implemented program is strictly limited to belonging to one of the implementation techniques - boost.statechart, visualState, etc.

    Obviously, such an approach narrows the space of opportunities that open up due to an automatically-oriented paradigm, and such an attitude to automata can be explained only by a lack of popular science material, which is fixable.

    What you want to use machines for is simplicity and, at the same time, design depth . In the previous part, it was shown that the basis for the automatic-oriented design of modules is the division of the task into an operational automaton ( OA ) and a control automaton ( UA ), and the operational automaton, in turn, can be re-divided into a lower-level operational automaton and its control automaton .

    An operating machine is a semi-finished product that can optimally perform some action, but at the same time it does not “care” when to perform this action and with what parameters. The operating machine can do this with any valid parameters. A great example of an ALU operational machine.

    In turn, the parametrization and start-up of the operating automaton rests on the shoulders of the control automaton. The multi-stage splitting avoids obtaining a complex control automaton with not obvious, albeit iron logic, replacing it with several simple control automata with the most understandable functioning.

    ImplementationIn this case, the control automaton can be completely non-automatic, or be automatic, but without such attributes as: states rolled up into separate functions, signal tables and corresponding transitions. And finally, I note that any program is automatic, and yet not all programs are automatically implemented.

    But in this case, what is meant by an automatically implemented program?

    Implementation: automaton vs not automaton.


    The main attribute of an automatically implemented program is:

    • the presence of clearly distinguished and clearly limited states. In operation, the program always is in one of the states.
    • the current state of the program is described by one single variable, which is called the internal state of the machine .

    This definition is an invariant, so to speak, the embodiment of which may be different. In the Methods for Implementing Automated Programs section, we will consider a number of examples that will illustrate what has been said, but in general the essence is clear.

    Now there is a clear criterion by which we attribute programs to automatically implemented programs, but someone will ask: what is the catch of automatic implementation, why is it more valuable in some cases?

    The main thing that distinguishes automatic-implemented algorithms from implemented ones lies automatically in the realm of our psyche, or rather how we think. As a colleague aptly remarked:
    “The human mind is designed in such a way that it is easier for him to understand the algorithms that feed the data at the input and receive the data at the output, and the result depends only on the input, but not on the internal state. It’s easier to understand, test and reuse such “pure functions” ( let’s call them analytical prim.aut. ). ”

    The behavior of the analytical function can be represented in the form of some table or graph: there is something at the input and there is a one-to-one correspondence at the output. However, the majority of digital devices are such that using analytic functions as bricks, as a result we still get a program whose behavior already depends on the internal state. That is, the use of analytical functions does not solve the problem of “comprehensibility”, moving it to another level!

    To illustrate the term “comprehensibility” and features of human thinking, I propose to consider how one and the same abstract algorithm is written, implemented automatically and non-automatically.



    a)



    b)

    Figure 2. A generalized example of a control device (a) and a graph diagram describing the operation of this device (b).

    A certain program is designed to control a certain device. As shown in Fig. 2a, the non-refined OA is controlled directly by the hardware, which is controlled by the UA, the operation algorithm of which is shown in Fig. 2 (b). UA processes external commands, conventionally indicated by the set of characters {0,1,2}, and translates them into a set of micro-instructions that control the operating machine. By microinstruction, I mean the set of commands needed to get the effect. Each set of micro-instructions is conditionally indicated by the symbol {1,2,3,4,5,6}. Flags {a, b, c} of the control machine monitor the state of the managed object , and, accordingly, determine the processing modes of the input command.

    Since this is a digital device with memory, the algorithm described in Fig. 2 is actually an automaton, despite the fact that the implementation of the algorithm is non-automatic. This leads to the fact that there are no explicitly allocated states in it , as a result of which the current state is implicitly determined by flags. Moreover, the description of the program by a graph-scheme does not in itself contradict the automaton principle; an automatically-implemented program can be described by a graph-scheme; there will be such an example. The main snag associated with the graph diagram is the low comprehensibility of the program described by the HS from the point of view of the dynamic, i.e. process flowing in time.

    Here's what I have in mind: this is a very simple example, but here it is impossible to say unequivocally which output signal will correspond to the input signal 0, because it will depend on the state of the flags, and more precisely the flag b, which in turn depends on what was at the entrance earlier. It’s also not easy to say straight away which output sequence will correspond to the input sequence: 2,1,0,2,1,0. To do this, you must actually execute the algorithm.

    In order to give a complete correspondence of the input and output signals, that is, to describe the function in the form of a table, it will be necessary to perform total testing, and besides, the result will be obtained in the form of two-signal sequences in which all kinds of input combinations are sorted in turn.


    Figure 3. Timing diagram - a way to describe the behavior of systems with memory.

    Since three binary flags allow tracking no more (but possibly no less) of the 8 previous characters, for an alphabet of 3 input characters, to describe all the possible options, we need to give 6561 diagrams, the so-called power of the product of the set of input signals and the set of states, which as the number of states and the size of the alphabet of input signals grows, it grows geometrically.

    Automated implementation of the program allows you to describe it using a state diagram, and the state diagram and transitions gives a radically different approach to the analysis of dynamic systems with memory. We will construct an automaton that implements the algorithm depicted in Fig. 2b (I will not specify how, this is the topic of another conversation), and which is described by the state diagram and transitions shown in Fig. 4. The state name on the diagram coincides with the output symbol when the automaton in this condition.


    Figure 4. The state and transition diagram corresponding to the algorithm depicted in Fig. 2.

    Using this diagram is very convenient, since only input characters affect transitions, there are no additional conditions. In other words, in order to analyze the response to the input symbol for implementing Fig. 2, you need to have the current state of the flags in each iteration, new, and in order to analyze the behavior of the device implemented as shown in Fig. 4, you need nothing but this diagram.

    This is an important advantage of an automated approach called:


    A look at dynamic processes outside the time axis.


    The human brain is arranged so that it is easier to work with a table of numbers than if the same table is shown one figure at a time. In the first case, a person is able to identify complex patterns; in the second, he can hardly determine any pattern, except for the simplest ones, even if you scroll the table cyclically.

    Consider an example, let us have a sequence of commands

    Set_position(6,0);
    Line_to (1,0);  Line_to (1,1);  Line_to (-1,2);  Line_to (4,0);
    Line_to (1,-3); Line_to (3,0);  Line_to (0,6);   Line_to (-11,0);
    Line_to (-1,1); Line_to (-2,0); Line_to (3,-2);  Line_to (0,-2);
    Line_to (1,2);  Line_to (2,0);  Line_to (-1,-2); Line_to (1,-1);

    Agree, each of the actions is simple in design. However, not having completed all the actions, we cannot say what we will succeed. The result of this algorithm is shown in Fig. 5 a


    a) b)
    Figure 5. The result of the execution of the sequence of commands (a), and the result of the execution of the same sequence, if an error is made (b).

    At the same time, I was mistaken in the calculations, and, for example, indicate in the first statement of the second line instead of (1, -3) the value (2, -3), the result of the work would be different (5 b), but looking at the text of the program of this cannot be understood. And this is a simple case when the result can be seen immediately after execution. If we saw the result as a single line at any given time, or if we were dealing not with graphics, but with numbers, our mistake would not be so obvious.

    This is not an easy kind of information for the human brain, called a dynamic process, as a sequence of actions (in the example, separate lines),giving as a result of the overlay some expected result (in the example figure).

    A good example of looking at dynamic processes outside the time axis is the analysis of signals in the frequency domain. Consider the signal in Fig. 6. In some ways, it can be compared with the time diagram of the automaton. This is also a sequence of actions: the signal crossed 0, went up, reached a maximum, went down, crossed 0 again.


    Figure 6. The signal graph, an analogue of the time diagram for automata.

    Obviously, this is a periodic signal, one can even guess that it consists of several sinusoids, but it is difficult for us to say which ones.
    At the same time, the spectrum directly gives us an idea of ​​the signal structure.


    Figure 7. The spectrum of the signal depicted in Fig. 6.

    The spectrum can be compared with the automaton diagram in this respect: it contains a static description of what lies at the heart of the process that takes place over time . Both the spectrum and the state and transition diagrams make it possible to analyze the process outside the time axis, covering it as a whole, and not as a sequence of steps.

    A bit of math


    A state diagram and transitions, as a rigorous mathematical category, enables in-depth analysis.

    Let us analyze the process described in the state and transition diagram of Fig. 5. For this we need the concept of an isomorphic automaton. Isomorphic automata are a mathematical term that means automata that are in fact the same automaton with renamed states and / or signals.


    Figure 8. Isomorphic automata.

    From the conditions of the problem it follows that we do not know anything about the processes that the algorithm in Fig. 2 b. Nevertheless, the analysis given in Fig. 4 diagrams allows us to identify two very similar clusters, switching between which is mainly done by signal 0.

    We construct an automaton that is isomorphic to the original one, but whose state numbers are renamed as shown in Fig. 9 and outline the indicated clusters on it. In a cluster with states 4,5,6 in parentheses are identical states of the first cluster.



    Figure 9. An automaton isomorphic to the one shown in Fig. 4 We

    decompose (split) the original automaton into two parallel automata, as shown in Fig. 10.


    Figure 10. Parallel decomposition of the automaton shown in Fig. 9.

    The output symbol of each of the automata is given a slash after the name of the state. The output symbols of the obtained automata are added arithmetically, giving the output symbols from 1 to 6, which fully correspond to the symbols at the output of the original automaton with the same input data. This connection of automata is called parallel composition.

    Pay attention to Automatic 2 . Whatever state it is in, input symbol 0 leads to the appearance of symbol 1, input symbol 1 to the appearance of symbol 3, and symbol 2 to the appearance of symbol 2. That is, in fact, this is a combinational circuit, an array of output symbols, and the array index is the input character. Let us depict the automaton as shown in Fig. eleven


    Figure 11. An automaton equivalent to the automaton shown in Fig. 10

    Since the output symbols we encoded a certain set of microinstructions, it might seem that arithmetic conversions are inappropriate here, however, if you look at the problem through the eyes of a mathematician and imagine that we have an array of implemented microinstructions in which each microinstruction has an index, in this case the correctness the transformations we have made are beyond doubt.

    I emphasize specifically, since the symbols 0,1,2 at the input and the symbols 1,2,3 at the output refer to different alphabets, it is impossible just to take and submit symbol 1 from the output back to the input. However, there can be such automata in which the input and output symbols belong to the same alphabet, in which case the output symbols of the automaton can be fed to its input. This is called a feedback composition . Paragraph 4.7 of the lectures is devoted to such compositions .

    From the conditions of the problem, the nature of the object, which is modeled by the algorithm, was not known.
    fig. 2b, and nevertheless, by analyzing and decomposing the automata, we established that the simulated phenomenon is based on two independent processes that contribute to the final result. And although in the case of an abstract example this gives nothing but an interesting observation, in the case of a specific task, the above analysis may reveal unobvious aspects of the simulated phenomenon, therefore it is interesting not only from the programming point of view, but also from an engineering point of view. For an engineer, an understanding of the processes underlying the phenomenon can correct the view of the device being developed and get an original technical solution that beats the essence.

    The considered example touches upon another important and useful property of automata, the concept of equivalent automata. The fact is that there can exist arbitrarily many automata with a different number of states (i.e., we are not talking about isomorphic automata), which will give the same response to the same input sequence. Accordingly, if you place them in a “black box”, then you cannot distinguish them by applying different sequences to the input and analyzing the response.

    In this case, some automata will be more “wasteful” in terms of the number of internal states, while others are more “economical”. Among the whole set of equivalent automata there will be an automaton with the minimum possible number of states, and it is called a minimal automaton. Moreover, there are algorithmic techniques for obtaining an equivalent minimum from any automaton. In particular, this property means that when drawing up a state diagram and transitions, one should not chase the minimization of the number of states, but one should achieve the most clear and complete picture. And although often the comprehensibility and ease of implementation are related, it may turn out to be more visual to present the result as a pair of automata, as in our example. After that, using mathematical algorithms you can find the equivalent minimal automaton.

    Since I have no intention to consider the theory of automata in this article, I will briefly list the basic mathematical operations that can be performed on automata: composition, decomposition, minimization, obtaining an automaton from a microprogram, obtaining microprograms based on an automaton, algebraic operations on automata (addition, comparison of automata ), construction of a simulating automaton, etc. Theoretical justifications and methods for performing these transformations can be found, for example, here .


    To summarize today's part. A characteristic feature of non-manual programming is that the state of a program at any given time is described not only by a software counter, but also by a number of internal flags. Term statewith a non-automatic style of programs, this is a kind of non-formalizable concept, meaning approximately that the program performs all the actions that TK requires. Nevertheless, as was shown above, even with the non-automatic style of the program, mathematically it is an automaton. She has states in a mathematical sense, but these states are not described anywhere. It is not known how many there are and what are the connections between them. Adding each new binary flag increases the number of possible states geometrically. In this case, many new states will be unattainable states that the program should never get into under any circumstances, but since in this case we do not explicitly select the next state, but it turns out to be a superposition of all flags, if the logic of at least one of the flags is incorrect, the program may jumping into forbidden states and there is no indicator that would demonstrate this. When we are dealing with flags that are actively changing, and the program’s path is winding and goes through many branches, until all fork options for all possible input characters are tested, we can only believethat after the twentieth iteration, the program will be in the exact state that we expect.

    In the case of an automatic implementation, a state is a mathematical category. At each moment of time it is uniquely determined, in particular by a software counter. We ourselves set the set of states that is needed to solve the control problem and for each state we explicitly choose, based on the needs, which state will be next if an X or Y command arrives . If there are not enough states, you can arbitrarily increase their number to the required one, unambiguously prescribing the connections between them.

    I want to be understood correctly. Implementing the program automatically, you are also not immune to typos or misconception. By improperly simulating the device, you can set the transition to the wrong state, but this is no longer a software design error, but an engineering error, i.e. it is not related to which path - automatic or non-automatic is selected. In case of non-manual implementation, a powerful source of potential logical errors is added to the same modeling errors and typos, the name of which is: a dynamic process as a sequence of actions that yield some expected result as a result of superposition .

    In the next part, we will return to the solid ground of practical algorithms by arranging competitions between two implementations of the “Display” example, one of which is developedautomatically, while the other does not, and also consider the iterative process using the modification of the automaton as an example for the “Display” example.

    List of recommended literature. If there is a terrific story about automatic machines, write to me, I will add.

    Lectures for beginners, for those who have forgotten and in general.
    Strong lectures with examples. Part 1
    Strong lectures with examples. Part 2
    Strong lectures with examples. Part 3

    Also popular now: