9: Automated programming: problem analysis

Automata tasks

Many programmer tasks are conveniently solved using methods whose formalization can be tables of states and transitions (for example, their collection can be found in [32] and on the site http://is.ifmo.ru).

Example 9.1.1 . Model of the changing system.

Let us model a dynamic or ecological system, which has fundamentally different behavior in different areas. Instead of combining the analysis of which region the point belongs to, and calculating the next state of the system, we can write several simple modules for modeling the behavior of the system in each of the areas (the only test that may be necessary, we came out with next step of modeling outside the region or not). As a separate module, a global control program is built that checks the state of the system and calls the corresponding computing module.

In this case, the gain is not so much in the length of the program, as in its visibility and modifiability (although it is these very important qualities of the program that novice programmers most often underestimate). But if at the entrance to a new area you need to do a number of organizational actions (in each area are different), and depending on their result, choose a further trajectory of the system, then the description in the form of an automaton becomes more and more advantageous.

If, when analyzing a task, it is possible to identify a set of states of the process being described, conditions for transition between states and actions associated with states, then it is appropriate to solve the problem using the methods of state tables. When analyzing such methods, Moore finite automata can be used.

Theoretically, Moore's automaton is represented as a transition matrix, the rows of which are the states of the automaton, and the columns are the input symbols ¹ . In practice, the input symbols can be considered the results of testing some conditions. Implicit in theory, but the most important in practice, the contents of each state of the automaton is a procedure leading to a global change in the state of the computational system. Such procedures are called actions .

Automata tables are often also presented as graphs , which is especially convenient when not all possible transitions between the two states are realizable. See, for example, fig. 9.1, where both the table and the graph are presented.

Fig. 9.1. State table Conversion graph.

Here, states are identified by sequence numbers, and effects by letters.

On the state table or on its graph analogue, all actions are assumed to be global by default, and each action is connected to recognizing which of the conditions listed on the edges that go out of it is fulfilled. Depending on which of them is fulfilled, the automaton goes into the corresponding state, which again, if it is not final, is associated with the action and recognition.

There is a variation of the concept of automata, which generates another method of automaton programming. In theory, the Miles automaton is different in that the result recorded on the automaton output tape may depend on the selected transition. In practice, actions in the table of states and transitions can be associated either with states (with graph vertices, Moore’s automaton), or with transitions (with arcs of a graph, Mealy automaton). Below you will see examples when both of these ² options naturally occur during programming. The Miles automaton computation model is better to use if the checks in each state are essentially different, and the Moore automaton model is if the checks are essentially homogeneous, as in Example 9.1.1. on transitions "), a method when actions are performed in states, we call transformations in states (abbreviated simply" in states ").

Note that it is natural to consider state and transition tables as non-deterministic, since after performing an action it may well be true that several conditions corresponding to outgoing edges may be true at once.

Attention !

In this case, we see one of the inexhaustible sources of errors in programs, which D. Gris first noted. If, in essence, the task doesn’t matter to us which of the actions will be performed, and the language (like the standard languages ​​in which people usually work) forces the transitions to be determined, either by ranking them in order or by forcing their conditions to be logically inconsistent there are difficulties. They are connected with the fact that, after a change, it was necessary to determine something differently, but it is no longer possible to distinguish which of the conditions are significant and which are inserted only for determination .

As was shown in our example, transition and state tables are a natural way of programming for a module dealing with global operations on an environment (these global operations themselves are usually programmed in a different style). For automaton programming, go to is typical, and here it is in place.

There are many specific methods of automaton programming that fit into the framework of the two main methods. Automata programming well demonstrates how practical methods for solving logically and mathematically, seemingly homogeneous problems vary. A small change in resource constraints - and, although the old methods tend to remain relevant, it is better to move on to others.

Basic structures of automaton programming

The information space of all blocks and procedures for automaton programming in the first approximation is the same: the state of the system modeled by a set of program actions. But in fact, many blocks or procedures work with subsystems. Subsystems, due to their autonomy, may have characteristics that are directly inaccessible to the general system, and limited access to the total system data space. Moreover, the subsystems can communicate directly, bypassing the hierarchically superior system (see Figure 9.2). Thus, the structure of the information space with automaton programming in general corresponds to that imposed by modern systems with developed modularity ³ . In systems of modularity there are concepts provided for using other modules, there are modules that automatically gain access to all concepts of a friendly module, and there are interfaces between modules.

Fig. 9.2. Information Space Systems

Light gray areas are the traditional overall context of a system and subsystem. Dark grays illustrate that accessibility can be one-way, and not only hierarchically. One of the systems can influence a part of the information space of the other, and the latter can only passively follow what a colleague has done. Areas connected by two-way arrows illustrate direct communication bypassing the hierarchy.

Historically, the first model of automaton programming, used both in practice and for theoretical studies, was the presentation of a program in the form of a flowchart (see, for example, Fig. 9.3), the nodes of which were states. The nodes of the flowchart are divided into five types:

• the initial vertex to which there are no inputs and where the variables or the state of the computing system are initialized;
• actions at which the procedure call or the operator is executed and after which the automaton unambiguously passes to the next state;
• recognizers that check the value of a variable or predicate and then transfer control to different addresses;
• connections with several inputs and one output;
• exit , hitting which, the program ends the work.

Fig. 9.3. Block diagram

The representation of programs in the form of flowcharts was appropriate for many classes of programs that were written in machine codes without programming automation tools. The flowcharts were then the primary means of planning program development and documenting them. Traditional flowcharts are the subject of study, in particular, theoretical programming (see Kotov’s books [16], [17]).

Transition tables conceptually contradict such a fundamental notion of programming as assignment. In the block diagram of the arbitrary form, it is extremely difficult to trace how the value of a variable will change, what dependencies exist between these variables, and so on.

Actions in automaton programming are global, and conditions are local. Checking the condition does not change the state of the entire system (none of its parameters or characteristics), it only translates the program itself into one or another state.

This is confirmed by the analysis of practical systems for the simulation of which it is convenient to use automaton programming. For example, opening or closing one valve in a pipeline system changes all flows in the system, and checking whether the valve is open is a local operation. Changing the temperature of the working substance in the system again affects all its characteristics, and it is possible to measure this temperature by taking readings of just one sensor.

Here we are faced with the need to clearly distinguish between external concepts describing a system that is associated with a problem to be solved by a program, and internal concepts of the program itself. For the system as a whole, the states of the automaton that models it or interacts with it are indifferent. For her, it is important what changes in her happen. Thus, the state of the memory of a computing system can be quite regarded as an external characteristic with respect to the program that runs in it.

The need for simultaneous and coordinated consideration of external and internal characteristics leads to the fact that when internal characteristics are fragmented and detailed (for example, when the automaton programming style is combined with assignments), the programmer becomes confused, the consistency of concepts disappears and errors occur.

Attention !

If you use arbitrary tables of transitions, then you need to make sure that assignments are encountered as rarely as possible, ideally do without them completely, or assign only values ​​to variables that are immediately used as a basis for selection in the operator type case .

The state and transition graph, also called the transition table, is a loaded directed graph G. A vertex is associated with each vertex of the graph G and a condition for each arc.

The condition AB associated with the arc leading from a to b is meaningfully interpreted as follows. When executing AB in state a, control is transferred to state b (or, in another sense, a transition is made along a given arc).

When the state and transition graph is used to document a program, the names of the states usually coincide with the names of the procedures that are executed in that state.

Software representations of the state graph

Note that the programmatic representations of the state graph strongly depend on the dynamics of a given graph. It is necessary to allocate four subcases.

1. The states and the transition table are rigidly defined by the problem statement (for example, such is the task of parsing). In this case, the best software representation of state transitions is go to , regardless of the size of the table.
2. The states and the transition table are revised, but fixed between two modifications of the task. With small table sizes, implementation is still preferable through transitions, and with large enough ones, its decomposition is necessary, and therefore it is often advisable to represent states by objects.
3. States and a table of transitions are dynamically generated before the execution of this module and are fixed at the time of its execution. The best way to implement is to set the transition table as a data structure and write an interpreting program for such tables.
4. "Live table": modified during execution. So far, we cannot provide methodological advice for such tables, although it is obvious that, despite external riskiness, this way is extremely advantageous for many adaptive response systems. It is necessary to discuss in advance that the modules rebuilding the table and the modules that execute it should be separated as strictly as possible.

Methods of actions in states and on transitions: analysis of states and table construction

In this section, a detailed demonstration of two methods of automaton programming based on the model of Moore and Mili begins. The method of working in them is almost the same, but, as is most often the case, a small and seemingly technical difference (to which actions are compared: states or transitions?) Generates two incompatible methods. Their incompatibility is not as gross as in many other cases (two such cases — incompatibility between automata and assignments and between cycles and recursions — are discussed below). If this is a contradiction, it is a technological contradiction. Randomly mixing these two methods, we further make it difficult to modify the program, and in the present we are forced to multiply the number of supports.

A person even ignores or ignores rough contradictions ⁴ . To apply the rule, it is important to know not only it, but also when it can be violated. The general methodological principle here is this: if we break, then to the fullest (having passed the intersection at a red light, it is foolish to stop right behind it)! The second principle: if it is impossible, but very necessary, then it is necessary! A. A. Shalyto pointed out that in theory ⁵ there is also such a mixed concept as Mili-Moore automata. One of the models of such automata is an automaton with two output tapes: on one the result is written in states, on the other - on transitions. The programmatic interpretation of such a theoretical model is, for example, a module that, in states, conducts a dialogue with the environment, as a result of which it receives data to determine the next transition, and performs internal calculations on the transitions.

To practice the technique, a simple task is used, which does not obscure its essence with particular subtleties and is suitable for implementation by either of the two methods. The resulting technique is transferred to a wide class of problems and does not fail up to thousands of states.

Problem statement and primary analysis

Suppose you want to solve the following problem. A word is any non-empty sequence of letters of the Latin alphabet (for simplicity, only lowercase letters). Reprint from the input sequence of characters all the maximum words in it in the following form:

-

Input ends with an empty string.

For example, in the lines

  hippo parrot
 1mot2krot1mot 

need to issue something like

  parrot 7
 hippo 7
 Mot 3
 mole 4
 Mot 3 

To solve a problem, it is natural to consider the input sequence of characters as a stream, readable from left to right, until an empty line is read. When reading letters, other characters and the end of a line, the actions that need to be performed are different. In addition, actions for the first letter and for subsequent letters of the word are distinguished.

Building a state graph

First of all, we define a set of states based on different reactions to the read character.

Here is a complete list of reaction options:

1. Symbol letter: initialize word processing (assign a unit to the word length counter).
2. Symbol letter: continue word processing (word length increment by one).
3. The symbol is not a letter: finish processing a word (type the length of the word read).
4. Symbol not letter: skip symbol.
5. End of line character: finish word processing (type the length of the word read).
6. End of line character: skip character.
7. End of line character: complete the process.

There is one more action that is not reflected in this list, but implied: the standard action that takes place before the start of the development of a new state. In this case, it is the reading of the next character that should be performed when the transition is triggered. In other cases of automaton models, the role of reading the next character can play, say, the next modeling step. For this and for most other automaton examples, the standard action does not need to be specified explicitly, since it automatically matches each transition and fully corresponds to the mathematical model.

From the list of actions for the task in question it follows that there should be at least two classes of states that have different actions-reactions.

The next method is the determination of the initial state, i.e., the one in which the computational process is activated. You need to specify what actions are possible in this state and what conditions of transition in it should be.

For the case under consideration in the initial state ( St1 ), transitions are possible:

1. with the transition to another state - St2 (since the next letter requires a different reaction),

4. preserving state and

6. working off the first line feed.

Fig. 9.4. Start building a state graph by Moore

The result of the analysis just performed can be represented as a graph shown in Fig. 9.4. С каждой дугой графа связано условие перехода. С каждым состоянием может быть связано действие. В состояниях St1 и St3 действием является пропуск очередного символа и чтение следующего, но соединить их сейчас нельзя, поскольку в первом из них переход на завершение работы невозможен, так что перевод строки анализируется по-разному. Это позволяет предположить, что в данной задаче действия стоит ассоциировать спереходами, а не с состояниями. Правильный выбор того, с чем ассоциировать действия, может сильно оптимизировать программу. Для показа двух возможных вариантов, которые в данном случае почти эквивалентны по сложности, мы будем действовать как на переходах, так и в состояниях. В частности, предварительный анализ состояний при методе преобразований на переходах дан на рис. 9.5.

Fig. 9.5. Начало построения графа состояний при использовании метода на переходах

Attention !

Если у Вас есть две близкие, но концептуально противоречивые, модели, в начале развития программы нужно сделать выбор в пользу одной из них. Небольшие эксперименты и отступления в начале оборачиваются большой экономией сил в конце .

На схемах вход и выход обозначаются черными прямоугольными блоками. При желании их можно считать специальными состояниями, с которыми ассоциированы действия инициализации и завершения процесса. Состояние St2 изображено штриховой линией, поскольку анализего еще не проведен. Для каждого из еще не проанализированных состояний (в данном случае для St2 ) следует определить условияперехода (и соответствующие им действия, если выбрали работу на переходах ).

In this case, in the St2 state , transitions are possible:

2. state saving;

3. ending a word and practicing word output, since the next character is not a letter, with a transition to another state, which is given the temporary name St4 ;

5. working out the end of the word and the line feed, you can give it a temporary name St5 .

After this construction, it is checked whether the new state is not a copy of the already existing ones both by actions and by transitions. If so, then the new state can be identified (glued) with one of the previously constructed. Newly appearing states are analyzed similarly.

Для решаемой задачи легко выяснить, что состояние St3 требует тех же действий и переходов, что и St5 , а St4 изоморфно St1 . Следовательно, возможна склейка этих двух состояний со старыми и построение графа завершается, так как новых состояний нет (см. рис. 9.6). С тем, чтобы не дублировать действия <Завершить процесс>, можно определить еще одно, заключительное состояние, с выходом из которого будет ассоциировано это действие (один раз!).

Fig. 9.6. Полученный граф состояний при действиях на переходах

Аналогично можно поступить и когда мы работаем в состояниях. Здесь процесс удлиняется на один шаг, поскольку необходимо выделить завершение обработки слова в отдельное действие (причем в двух вариантах: после перевода строки и после других небуквенных символов). Полученный результат показан на рис. 9.7.

Fig. 9.7. Полученный граф состояний при действиях в состояниях