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

Abstract

Contents

Introduction

Using the model of finite automata to describe the various discrete systems and processes is the most practical method of submission. However, to fully understand the need to take into account the fact of the possibility of external factors that can change the behavior of a state machine and the entire system. Exposure could be any local transformation on the initial state of the machine. In view of this there is a need to analyze the behavior of the two states of the automaton and the converted source and compare them. In this paper we study the behavior of a state machine for local transformation.

1. Relevance of the topic

Finite state machine model may be useful in describing the interaction of different types of objects, as in the technical problems of building management systems, and in the task of describing the behavior of any object where you want to explore the concept of the state, the impact of the input parameter and as a result – a reaction to it. So the theory of machines used in the development of formal languages ??and programming languages, and programming with the direct writing programs, the so–called automata programming. In practical terms, implementation of a finite state machine is in any computing device.

Therefore, the relevance of the study model of finite automata is obvious, and as a consequence, it is important to study the behavior and finite state machine for local transformation.

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

The aim of the research is the development and study of the impact of the method of assessment of local transformations of the behavior of a finite state machine.

The main objectives of the study:

  1. To analyze the behavior of the original machines and generates a transformation derived from the transfer of the arc.
  2. Assess the degree of proximity to any transfer of arcs.
  3. A description class structure is locally generated by machines, breaking it into subclasses machines, which are equivalent as far as the proximity of their behavior behavior initially given automaton.

The object of study: the behavior of finite automaton given under local transformations.

Subject of research: finding the degree of closeness of the original behavior of the machine and the machine resulting from the impact of local transformation in the form of a sequence of arcs rendition in the transition graph of the original machine.

3. Model of machine

Let us compare the behavior of automata in the local transformations resulting from rendition arcs take particular case as starting the machine will be considered definitely diagnosed of order k automaton, and a local transformation we mean the transfer of exactly one arc.

Mealy automaton A = (S, X, Y, δ, λ, s0) to be used as an initial powered ML–k, where S – is a finite set of states, X, Y – finite sets of input and output, δ, λ – is transition and output functions, and s0 is taken as the initial state. Index A or touch the icon is added to the designation of these objects, if necessary, to avoid confusion.

Machine A is called an automaton definitely diagnosed of order k, if k≥1 – the smallest integer such that for any input word p of length k and any pair of different states s, t∈S the inequality λ (s, p) ≠ λ'(t, p).

Equivalent called two states s and t the same machine A, or two different machines A and B, respectively, if for any input word r∈X* is the condition λ (a, p) = λ'(b, p), where λ '– the output function of the automaton A or B. We have so called automatic provided that all its states nonequivalent.

The functions δ and λ are distributed in the usual way on the set X* of all input words of finite length in the machine.

Let w = (p, q) – input–output word, it is generated by the state s of the automaton A if λ (s, p) = q. The length of the word w is denoted |w|.

For each state s in line put a lot λs all input–output words that generate pairwise nonequivalent states of the automaton. The behavior of the automaton A will be understood by a variety of λs0 input–output words that are generated by its initial state.

The most convenient to set the machine in the form of a transition graph whose vertices correspond to the states of S, and the arc will be fours (s, x, y, t), at t = δ (s, x), y = λ (s, x). The mark is a pair of arc (x, y), the beginning of the arc – s, the end of the arc – t. When e = (t, x, y, u) – arc in the graph of the automaton A, transfer of the arc from the state u to state v, other than u, will be named to replace it with the next arc –(t, x, y, v) .

4. The task of analyzing the impact of changes in the local behavior of finite automata

Research machines with similar behavior in one sense or another, as well as the structure of their classes [1] continues for a long time, mainly due to the development of the theory of experiments with automata. The base of the theory of experiments with automata was initiated by Moore [12], then it was first proposed algorithm for determining equivalence machines.

The work of Gill [1] F. Hennie, M.P. Vasilevsky, A.M. Bogomolov [10], I.S. Grunsky [2, 3, 8] S.V. Yablonsky, I.K. Rystsova, N.V. Yevtushenko, V.A. Tverdokhlebova, A.F. Petrenko, as well as many others on the theory of experiments.

Now the theory of experiments and then continued its intensive development among academics, the study of the effect of changes in the behavior of the local machine, obtained important result. That influence rendition arcs on the graph of the automaton behavior machine given in [3–7 , 9]. After examining the operation, we found the following conclusions:

5. Bringing theoretical results

Consider the structure of a locally generated class. The following theorem shows how the distance between two connected locally generated machine guns and two parameters: d – the length of the shortest word that translates machine from an initial state to a state that will be transferred from the arc, and k – setting ODk machine.

Theorem 5.1. Let A be – given an initial OD–k–machine and A' is obtained from A by switching the arc (t, x, y, u) in the state v. Then ρ (A, A') ≥ 1/(d + k + 1), where d – length of the shortest of the input word w such that δ (s0, w) = t.

Proof. To distinguish from the state machine A state A', will mark the status of the last touch and a pair (s, s') is called the dual where s∈S, s'∈S'. We first show that the state of u and v' are distinguishable by some word of length at most k. For this we use techniques that used in the proof of the fact that the transfer of the arc in any given machine always leads to the automaton is not isomorphic to the source [7]. We construct a machine in equal to the direct sum of automata A and A ', and consider the process of constructing Pi tables [11] for the machine B.

Since the output table machines A and A 'coincide, the table P1 each equivalence class consists of pairs of dual states. Note that any pair of (s, s '), except for the pair (t, t'), according to any x again passes into a pair of dual states. Couple (t, t') – the only one for which it is not satisfied as δB (t, x) = u and δB (t', x) = v '. This implies that while the state (t, t') k–equivalent, any pair of (s, s'), different from (t, t'), is (k + 1) –equivalent. The very same pair (t, t') k–equivalent, while the pair (u, v') is (k–1) – equivalent. But, if (u, v') (k–1) –equivalent, then the pair (t, t'), (u, u'), (v, v') k–equivalent, and hence the state of u, u', v, v' belong to the same equivalence class table Pk. Since A ML–k–automatic, then for some i

Now let w – the shortest word in the input automaton A, transforming it from an initial state to t, u p – the shortest word discriminating u and v '. Let |w| = d, |p| = i, and as shown above, i≤k. It is clear that machine A' δ (s'0, w) = t'. Then δ (s0, wx) = u, δ (s'0, wx) = v ', λ (s0, wx) = λ (s'0, wx), but λ (s0, wxp) ≠ λ (s'0, wxp), moreover |wxp| ≤ d + 1 + k, as required.

We show that the resulting estimate of the distance achieved. Figure 5.1 shows an initial autonomous automaton A. Let the automaton A' is the result of a transfer of the arc in the automaton A: arc (6,0,2,5) is thrown into a state of 3, and is replaced by an arc (6',0,2,3'). Since being transferred arc emanating from a state 6, the shortest word w has the length d = 3. It is easy to see that λ (s0,0000) = λ(s'0,0000), but λ(s0,00000) ≠ λ (s'0,00000). Therefore wxp = 00000 and |wxp| = 5. Hence ρ(A, A') = 1/5. For example, it is clear that as a result of transferring the arc machine A 'became a given machine, as state 5 and 6 steel equivalent.

An example of one transfer arc machine ML–2

Figure 5.1 – Example of a transfer arc machine ML–2
(animation: 2 frames, 7 of repeat cycles, size - 377×233, 5,22 KB)

Theorem 5.2. Let A – an initial and reduced automaton A' is obtained from A by switching the arc (t, x, y, u) in the state v. Then ρ (A, A') ≥1 / (d + n), where d – length of the shortest of the input word w such that δ (s0, w) = t.

Theorem 5.3. Class Ki (A) consists of all automata A', for which the following condition: d + a + 1 = i.

Complete the proof of Theorem 5.2 and Theorem 5.3 will be given in the text of the master's work.

Conclusion

In this paper we were obtained the following results:

  1. The evaluation of the degree of closeness of conduct initial automata and machine derived from the initial target in the transfer of a single arc.
  2. The structure of classes automata with a given degree of proximity to the behavior of a given machine relative to baseline.
  3. The above description of the structure of classes can be taken as the basis of the algorithm for constructing them.

In writing this essay master's work is not yet complete. Final completion: December 2015. The full text of work and materials on the topic can be obtained from the author or his supervisor after that date.

References

  1. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. – 270 с.
  2. Грунский И.С., Козловский В.А., Пономаренко Г.Г., Представления конечных автоматов фрагментами поведения. – К.:Наукова думка, 1990. – 231 с.
  3. Грунский И.С., Копытова О.М. О структуре контрольного эксперимента для определенно–диагностируемого автомата // Теория управляющих систем. – К.: Наук.думка, 1987. – С. 45–50.
  4. Копытова О.М. О возможности сохранения поведения автомата при перебросках дуг // Материалы VI Международной научно–практической конференции Новости научной мысли – 2010 (27.10–05.11.2010), Чехия. Прага. Издательский дом Образование и наука, 2010 – C. 35–46.
  5. Копытова О.М. Устойчивость автоматов к неисправностям их функции переходов // Труды ИПММ АН Украины. – 2010. – № 21. – С. 55–63.
  6. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг // Труды VIII Международной конференции Дискретные модели в теории управляющих систем. – М.: Макс–Пресс, 2009, C. 150–158.
  7. Козловский В.А. О структуре контрольных экспериментов с автоматом // Кибер нетика. – 1978. – № 3. – С. 20–31.
  8. Кудявцев В.Б., Грунский И.С., Козловский В.А. Анализ и синтез абстрактных автоматов //Фундаментальная и прикладная математика. – Т. 15, № 4. – 2009. – С. 90–180.
  9. Бурлаева Е.И., Копытова О.М. Об одном типе локальных преобразований автомата // Материалы IV всеукраинской научно–технической конфиренции студентов, аспирантов и молодых ученых Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013) (24.04–25.04.2013). Донецк: ДонНТУ, 2013. – C. 480–485.
  10. Богомолов А.М., Барашко А.С., Грунский И.С. Эксперименты с автоматами. – Киев: Наукова думка, 1973. – 144 с.
  11. Чивилихин Д.С., Ульянцев В.И. Метод построения конечных автоматов на основе муравьиного алгоритма // Технологии программирования, искусственный интеллект, биоинформатика. – 2013. – С. 235.
  12. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами // Автоматы. – М. : Иностр. лит. – 1956. – С. 179–210.