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

Content

Introduction

The theory of automata is one of the most important branches of discrete mathematics and computer science. Many hardware and software components software are modeled by finite state machines, and when designing event systems, more and more program code for the target platform is generated according to the created automaton model. The main advantages in the design and analysis of programs using finite state machines are visibility of their presentation in the form of state diagrams and increasing the level of automation of the verification process by the method of model checking (model checking).

The finite state machine model is widely used to describe and analyze the behavior of various devices of discrete action or flow discrete information processing processes, for modeling and building devices and processes. These devices and processes can undergo changes due to external influences, which in turn can lead to a change in the behavior of the automaton or leave the behavior automaton unchanged. This gives rise to the problem of studying automata with behavior similar in one sense or another, as well as the structure of classes such machines. Problems of this kind were considered, in particular, in the theory of experiments with automata. In practical terms, of interest are such transformations under which the behavior of the automaton remains unchanged, i.e. the automaton "shows resistance" in behavior to external influences. In the general case, the recognizer does not give an exact indication of how to proceed at the next step, but allows the computational the process in several ways. Therefore, not all state machine recognizers are suitable for constructing recognizers suitable for practical applications.

PROBLEM STATEMENT

A recognizer (acceptor) is an automaton that allows you to determine whether a string of characters belongs to a certain language. A task the recognizer is to give an answer based on the original string, whether it belongs to the given language or not.

A deterministic finite automaton A is a five of objects A = (S, X, b, s0, F) , where S is a non-empty finite set states, X is the final input alphabet, s0 is the initial state, b: SxX-> S is the transition function, F is the set of final states. The set of all input words p that transfer the automaton from the initial to one of the final states is called the language L (A), recognizable machine. Let Lk (A) denote the subset of the set L (A) consisting of words of length <= k. We say that automaton A generates language Lk (A), and the state s generates the set Lk (s) of words of length k.

Two state machine recognizers with the same input alphabet are said to be equivalent if they recognize the same language, those. L (A) = L (B) . By the well-known Moore theorem [1], two recognizer automata are equivalent if and only if under the action of one and those however, they always end up both in the final or both in non-final states of the input words.

In what follows, by an automaton we mean a reduced deterministic acceptor.

The task of the research is to find such sets of jumps of arcs, for which an acceptor A 'is obtained, indistinguishable from A by experiments a given length.

AUTOMATIC REPRESENTATION STRUCTURE

A state machine is a model that is convenient to use in a wide variety of areas, from modeling logic devices in technical diagnostics to structuring applications. In particular, one of the applications of finite state machines is the simulation of faults in discrete devices. Such faults can often be described as the transfer of arcs in the machine while saving output reactions.

Of interest are such transfers that change the behavior of the machine. A number of works are known in which the properties of such transfers are investigated. In this paper, we continue to study the properties automata subject to the transfer of arcs and monitoring its further degradation.

Moore automaton state diagram

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

The state machine model went well the test of time. The use of state machines allows developers to create well-organized logic systems with flexible capabilities, and analyze their behavior in various conditions.

For example, games often use different characters that move around the game area and can act in different modes. Using state machines with well-defined rules for each character, defining the possible options for his behavior in various states and permissible transitions from one state to another, allows you to create complex behaviors as characters, computer-controlled and user-controlled characters.

Deterministic state machine

A deterministic finite automaton (DFA) is a machine that recognizes strings of characters, in which for each sequence of input characters 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 finite state machine A can be represented in the form of a five A = (S, X, b, s0, F) , where

  1. S - a finite set of states of the control device;
  2. X - alphabet of input characters;
  3. b is a transition function that maps S x (I U {i}) to the set of subsets of the set S;
  4. s0 - initial state of the machine;
  5. F is a set of final (accepting) states.

Figure 2 - Deterministic finite state machine

The DCA performs steps determined by the current state of its control unit and the input symbol viewed by the input head. Each step consists of a transition to a new state and a shift of the input head by one cell to the right. That a language can be represented by a regular expression if and only if it is allowed by some state machine.

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 transition functions. It is a loaded unidirectional graph, the vertices of which are the CA states, edges are transitions from one state to another, and load are symbols at which this transition is carried out. If the transition from state a1 to a2 can be carried out when one of several symbols, then all of them must be inscribed above the arc of the diagram (branch of the graph).

A jump table is a tabular representation of a function F. Typically, in such a table, each row corresponds to one state, and a column has one valid input character. In a cell at the intersection of a row and a column the action to be performed by the automaton is recorded if, in a situation where it was in this state at the input, it received the given character.

Non-deterministic state machine

A non-deterministic state machine is an abstract machine that reads characters from an input string and decides whether to accept or reject that string. He can change state by going from one state to other. The internal structure of such an automaton can be represented by a transition graph. An NFA also recognizes strings of characters, a chain is considered valid if, after its processing, a set of states turned out to be an automaton that contains at least one admitting one. Thus, the NCA also defines some language.

Any non-deterministic state machine can be transformed into a deterministic one so that their languages coincide and such machines are called equivalent. However, since the number of states in equivalent DFA in the worst case grows exponentially with the growth of the number of states of the original NFA; in practice, such a determination is not always possible. In addition, finite state machines with output in general case do not lend themselves to determinism.

For each state and each input symbol, the NCA has zero or more options for choosing the next step. It can also choose whether to move its input head when the state changes or not. Let us give definition of a non-deterministic state machine.

There is an additional result or the possibility of comparing an equivalent "deterministic" machine to any taken NCV. However, a deterministic finite automaton equivalent to a given NFA with n states, can have up to 2 to the n power of states. Therefore, the transition from an NFA to a deterministic FSM does not always provide an efficient way to model a non-deterministic FSM.

Conclusions

The paper considers a number of examples showing the existence of transfers that preserve Lk (A), and showing how the indicated transfers can be determined.

These examples lead to the following procedure.

A sequence of tables P0, P1, ..., Pk is built, and the classes in the table Pk are considered. If Pk contains at least one class containing more than one state (s and t), then for the states of this class the required transfers. These transfers are specified using Рк-1 so that the receiving state for any x for s and for t does not go beyond the class to which the ends of the arcs (s, x, y, u) and (t, x, y, v). If in Pk all classes are one-element, then transfers are impossible.

In what follows, this procedure is supposed to be presented in the form of an algorithm.

LIST OF SOURCES

  1. Кудрявцев, В.Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М. : Наука, 1985. – 320 с.
  2. Капитонова, Ю.В. Основы дискретной математики / Ю.В. Капитонова, С.Л. Кривий, А.А. Летичевский, Г.М. Луцкий, Н.К. Печурин. – К. : Наукова думка, 2002. – 568 с.
  3. Брауэр, В. Введение в теорию конечных автоматов / [пер. с нем]. – М.: Радио и связь, 1987. – 392 с.
  4. Копытова, О. М. Устойчивость автоматов к неисправностям их функции переходов / О. М. Копытова // Тр. ин–та ИПММ АН Украины. - 2010. - № 21. - С. 57-66.
  5. Копытова, О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг / О. М. Копытова // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем». – М.: Макс–Пресс. – 2009. – С. 155-159.
  6. Богомолов, А.М. Эксперименты с автоматами / А.М. Богомолов, А.С. Барашко, И.С. Грунский. – Киев : Наукова думка, 1973. – 144 с.
  7. Евтушенко, Н.В. О проверяющих возможностях кратных экспериментов / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1989. – № 3. – С. 9-14.
  8. Кудрявцев, В. Б Анализ поведения автоматов / В. Б. Кудрявцев, Грунский И. С., Козловский В. А. // Дискретная математика. – 2009. – Т. 21. – №. 1. – С. 3-35.