Українська   Русский
DonNTU   Masters' portal

Summary of the final work

Content

Introduction

State machine – a model that is convenient to use in a variety of areas, ranging from modeling logic devices to technical diagnostics and ending with the structuring of applications. AT In particular, one of the applications of finite automata is simulation faults discrete devices. Often such faults can describe as the transfer of arcs in the machine while maintaining the output reactions.

Displays that change behavior are of interest. automat. A number of papers are known in which properties of transfers are investigated. this kind. This paper continues the study of the properties machines subject to the transfer of arcs and monitoring its further degradation.

1. Relevance of the topic

The state machine model has gone through a good test of time. The use of finite automata allows developers to create well-organized logical systems with flexible capabilities, and also analyze their behavior under different conditions.

For example, games often use different characters that move around the game and can operate in different modes. Use of finite automata with well-defined rules for each character, determining the possible variants of his behavior in different states and allowable transitions from one state to another, allows you to create complex behaviors like characters, computer-controlled as well as user-controlled characters [ 1 ].

This paper relates to the theory of experiments with automata. By experiment call the process of filing on the machine sequence of input signals, observation of the corresponding reaction of the machine and the conclusion of the functioning and properties of the automaton based on these observations and a priori information about the machine. The main task of the theory of experiments consists in the development of effective experiments, allowing to obtain certain information about the structure of the machine, its functions, the characteristics the process of converting information carried out by this automaton.

Thus, the study of the model of a finite automaton and the study of it behavior is an urgent task.

2. The purpose and objectives of the study, the planned results

The object of the study is the behavior of the end when transferring arcs.

The subject of research is the study of the method of constructing the function of degradation of the behavior of a finite automaton as a result of the transfer of arcs.

The goal of the master’s thesis is to develop and research a method for constructing a function of degradation of the behavior of a finite automaton as a result of the transfer arcs.

The main tasks of the work:

Moore State Machine State Diagram

Figure 1 – The transfer of 4 arcs in the machine
(animation: 17 frames, 3 cycles of repetition, 82.1 kilobytes)

3. Review of research and development

Automata similar in behavior in one sense or another are explored. for a long time, as well as the structure of classes of such automata. AT This problem is mainly considered within the framework of the theory of experiments with automatic machines.

The basis of the theory of experiments with automata was laid by Moore. In his work, the study was conducted in two directions: the indistinguishability of automata by any multiple and no simple experiment, as well as recognition of the automaton and its states through such experiments. In the future, the theory of experiments was developed in the works of F. Henny, Miles, Brauer and others. Methods and results of the analysis of automata and algorithms for conducting experiments with them are fully represented. in the famous book of A. Gill.

Domestic work in the field of experiments with automata related with the names of A.M. Bogomolov and his disciples, MP Vasilevsky, V.N. Noskova, N.V. Evtushenko, A.F. Petrenko, I.K. Rystsova, V.A. Tverdokhlebova, S.V. Yablonsky, VB Kudryavtseva and others.

The theory of experiments is developing intensively in the present. In [ 2 - 4 ] A number of results were obtained related to behavior analysis. machines in terms of exposure to environmental factors. In a number of works, the effect of the transfer of arcs on the behavior of an automaton was studied. In graph theory, related problems were also considered, where the task of determining when one of the graphs (automaton) can be obtained from another as a result of some sequence of rendition of arcs.

4. Arc transfer example

Recall that the transfer of a single arc always leads to a non-isomorphic automaton. It is easy to give examples when the transfer to the automaton of the two arcs also generates a new automaton that is not isomorphic to the original.

In [ 4 ] sufficient conditions for the conservation were formulated behavior of the machine when transferring two arcs, and it was shown that any natural k & gt; 1 there is a reduced automaton in which there is a subset of k arcs, the simultaneous transfer of which leads to an isomorphic automaton. In [5], it was proved that when transferring The two input-output arcs on these arcs coincide. There were also examples of not strongly connected automata that allow the transfer of several arcs, and it was suggested that the states of which arcs are thrown are not reachable from those states where transfer is directed.

Let us give a number of examples when a transfer does not change the behavior of the original automaton.

The graph A (see Fig.2) is the result of the transfer of two arcs in column A: the arc (6, 0, 0, 8) is transferred to state 9 and is replaced by the arc (6, 0, 0, 9 ) , the arc (7, 0, 0, 9) is replaced by the arc (7 , 0, 0, 8 ). It is easy to see the mapping : A > A , for which (1) = 1 ; (2) = 2 ; (3) = 3 ; (4) = 4 ; (5) = 5 ; (6) = 7 ; (7) = 6 ; (8) = 8 ; (9) = 9 , is an isomorphism of the graph A onto the graph A .

Пример изоморфизма автоматов при переброске двух дуг

Figure 2  – An example of isomorphism of automata when transferring two arcs

In this example, the components of the strong connectivity of the automaton A are sets of states {1,2,3,4,6,7}, {5}, {8,9}, and throw arcs adjacent to different components.

5. Analysis of the main types of finite automata

5.1 Deterministic state machine

A deterministic state machine (DFA) is a machine that recognizes character chains, in which for each sequence of input symbols there is only one state in which the automaton can go from the current one (Fig. 2). It has an input tape, divided into cells, a head on the input tape (input head) and a control device with a finite number of states. The state machine M can be represented as a five (S, L, a, s, F), where

  1. S is a finite set of control device states;
  2. L is the alphabet of input characters;
  3. a is a transition function mapping S x (I U {i}) to the set of subsets of the set S;
  4. s - the initial state of the control device;
  5. F is the set of final (admitting) states [ 5 ].
DKA

Figure 3  – Deterministic state machine

The DFA performs the steps determined by the current state of its control unit and the input symbol viewed by the input head. Every step consists of a transition to a new state and a shift of the input head one cell to the right. That a language is represented by a regular expression then and only when allowed by some state machine [ 6 ].

A state machine can be described using state diagrams and transition tables.

A state diagram (or sometimes a transition graph) is a graphical representation of a set of states and a transition function. Represents 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 load is symbols, with who made this transition. If the transition from state a1 to a2 can be made when one of several characters appears, then all of them should be inscribed above the arc of the diagram (the graph line) [ 7 ].

The transition table is a table representation of the function F. Usually in such a table, each row corresponds to one state, and the column has one valid input character. In the cell at the intersection of the row and column, an action is recorded that the machine should perform, if in a situation where he was in this state at the entrance he received the given symbol.

5.2 Nondeterministic Finite Automata

A nondeterministic state machine is an abstract machine that reads characters from the input chain and decides whether to allow or reject. this chain. It can change state by going from one state to another. The internal structure of such an automaton can be represented by a graph The NCA transitions also recognize chains of characters, the chain is considered admissible if, after processing it, a set of states in which it turned out to be machine, contains at least one admitting. Thus, the NKA also sets some language [ 8 ].

Any non-deterministic finite-state machine can be transformed into deterministic so that their languages match and such atoms are called equivalent. However, since the number of states in an equivalent DFA at worst grows exponentially with an increase in the number of states source NCA, in practice, such determination is not always possible. In addition, finite state machines with access in the general case are not amenable determinism.

For each state and each input symbol, the NCA has zero or more choices for the next step. He can also choose shift the input head when the state changes or not [ 9 ]. We give the definition of a non-deterministic finite state machine.

There is an additional result or possibility to compare an equivalent "deterministic" machine to any taken NKA. However, a deterministic finite automaton equivalent to a given NCA with n states can have up to 2 to n degrees of states. Therefore, the transition from the NCA to the deterministic automaton does not always provide an efficient way to simulate a non-deterministic finite automaton [ 10 ].

Findings

The idea inite automata is an extremely useful concept, the fruitfulness of which has passed the test of time. The use of finite automata allows developers to create well-organized applications with flexible capabilities. Their use allows you to create a clear, understandable and reliably functioning code.

The use of state machines has become a common practice when designing applications for desktops, servers and mobile devices.

The advantages provided by the use of state machines are most noticeable in the case of mobile applications. requiring economical expenditure of screen space, memory, computing power and other resources.

List of sources

  1. Смирнова Н.В., Смирнов В.В. Применение теории конечных автоматов в разработке программных систем / Н.В. Смирнова, В.В., Смирнов // Збірник наукових праць Кіровоградського національного технічного університету. Техніка в сільськогосподарському виробництві, галузеве машинобудування, автоматизація. – 2014. – Вип. 27. – С. 316-320.
  2. Капитонова Ю.В. Основы дискретной математики / Ю.В. Капитонова, С.Л. Кривий, А.А. Летичевский, Г.М. Луцкий, Н.К. Печурин. – К.: Наукова думка, 2002. – 568 с.
  3. Евтушенко Н.В., Петренко А.Ф. Метод построения проверяющих экспериментов для произвольного недетерминированного автомата / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1990. – № 5. – С. 73-76.
  4. Кудрявцев В.Б., Грунский И.С., Козловский В.А. Анализ поведения автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский // Дискретная математика. – 2009. – №1. – С. 3-35.
  5. Козловский В.А., Копытова О.М. Представления автоматов относительно m-плотных классов / В.А. Козловский, О.М. Копытова // Матер. VIII Межд. семинара «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.) – М.: Изд. МГУ. – С. 277-280.
  6. Швец О.С., Копытова О.М. О сравнении поведения ОДk-эталона и автоматов, порождаемых его локальными преобразованиями / О.С. Швец, О.М. Копытова // Материалы V всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2014)» (22.04-23.04.2014). Донецк: ДонНТУ, 2014. – С. 365-369.
  7. Паулин О.Н. Основы теории алгоритмов: учебное пособие / О.Н. Паулин. – Одесса: Автограф, 2005. – 188 с.
  8. Гилл А. Введение в теорию конечных автоматов / А. Гилл. – М.: Наука, 1966. – 272 с.
  9. Брауэр Р. Введение в теорию конечных автоматов/ Р. Брауэр. – М.: Радио и связь, 1987. – 392 с.
  10. Евтушенко Н.В., Лебедев А.В., Петренко А. Ф. О проверяющих экспериментах с недетерминированными автоматами / Н.В. Евтушенко, А.В. Лебедев, А.Ф. Петренко // Автоматика и вычислительная техника. – 1991. – № 6. – С. 81-85.