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

Abstract

Content

Introduction

The model of the finite state machine is widely used for the description of various discrete systems and processes. These systems can be exposed to external distorting effects, and as result, to change the behavior. In many cases such effects have local nature and can be described by system of local conversions above arcs of the initial state machine. So, there is a task of the comparative analysis on behavior of the initial and transformed state machines and computation of closeness of these state machines by behavior. In this work the influence of one arc transfer on the initial definitely diagnosable of order k (DD–k) state etalon is being investigating. We are interested in this investigation from the point of view of determining a level of closeness of the machine behavior before and after arc transfer.

1. Theme urgency

Theoretical and practical meaning of state machines models in research of formation processes and signal transmission in complicated systems, the solution of technical tasks diagnosing and designing became the reason of intensive researches of the state machine theory as mathematical model of complicated systems. Now practically in any sphere of human activities meets the system concept. The finite state machine is one of the simplest mathematical models of complicated systems.

State machines are widely used in different areas of information defense. In particular, they naturally give opportunity to describe the stream crypto algorithms. Therefore research of the finite state machine model and the state behavior machine is urgent.

2. Goal and tasks of the research

Research object: initial finite state machine behavior.

Research subject: finding the shortest input word length that distinguishes the initial state machine and the state machine, received as a result of some arcs transfers in its transitions graph.

The purpose of master’s work is the development of the method for analysis of the state machines that are generated by local transformations of initial state machine.

Main tasks of the research:

  1. Тo carry out the comparative analysis of DD–k–initial state machine behavior and the state machine generated by its local transformations.
  2. The search of closeness measure of etalon behavior, which is an initial DD–k–machine, and the behavior of the machine, derived from the etalon by arc transferring.
  3. To evaluate a closeness measure ρ(A, A′) for any transfer of an arc.
  4. Let K(A) the class of all state machines locally generated from the etalon A. The task is to describe the structure of this class in terms of dividing it into sub–classes of automata that are equivalent by the closeness of their behavior to the etalon.

3. State machine model

We begin comparing of the finite state machines behavior received as a result of transfers of arcs, from the special case: as a etalon we will consider the DD–k–state machine and we will study the transfer of exactly one arc.

Under the model of state machine we will understand initial reduced DD–k Mealy state machine A = (S, X, Y, δ, λ, s0), where S, X, Y – are state, input and output sets respectively, δ, λ – the transition and output function, and s0 – initial state. If necessary to designations of these objects the index A or a stroke icon is added.

The state machine A is called initial, if some state s0, which is called initial, is selected in the set of its states.

In state machine the functions δ and λ normally apply to a lot of X* all input words of finite length. We will remind that the state machine A is called DD–k–state machine if k≥1 – the smallest whole such that for any input word p of length of k and any couple of different states of s∈S is executed an inequality λ(s, p) ≠ λ′(t, p).

5. The obtained theoretical results

Theorem 1. Theorem 1. Let A is initially reduced DD–k–state machine and A′ is received from A transferring arc (t, x, y, u) to state v. Then ρ(A, A′)<1/d+k+1, where d is length of the shortest word w, such that δ(s0,w)=t.

Demonstration. In order to distinguish state of the state machine А by state of the state machine А′, state of the last we will mark using hatch and the pair (s, s′) call duals, s=S, s′=S′. At first, we show, that states of u and v′ are distinguishable some word of length? Which is not longer then k. For this, we use the method, using for proving these fact, that transferring arc in any reduced state machine always leads to state machine, which is not starting isomorphic [7]. To construct the state machine B, which is equal to the direct sum of state machines А and А′, and to consider the process of constructing the Pk–spreadsheets [3] for state machine B.

Because the output spreadsheet state machine А and А′ coincide, then each equivalence class consists of pairs of dual states in the spreadsheets P1. Note that any pair (s, s′), except for a pair (t, t′), for any x changing back to a pair of dual states. Pair (t, t′) is the only one for which it is not, because δB(t, x)=u and δB(t′, x)=v′. It follows from this, that while the states (t, t′) k are equivalent, any pair (s,s′) is different from the (t,t′), and they will be (k+1) equivalent. The same pair (t,t′) (k is equivalent, while the pair (u,v′) is the (k-1) equivalent. But, if (u,v′) (k-1)–equivalent, then the pairs (t,t′), (u,u′), (v,v′) k are equivalent and therefore the states u, u′, v, v′ belong to the same equivalence spreadsheet Rk. As А DD–k–state machine, then for some i<k states u and will (i-1) be equivalent, but are distinguishable. And then i distinguishable will be states u and v′, where i≤k.

Let w is the shortest input word in the state machine A, transforming it from an initial state to state t, and p is the shortest word discriminating u and v′. |w|=d, |p|=i, and as shown above, i≤k. It is clear that in state machine А′ δ(s′0,w)=t′. Then δ(s0,wx)=u, δ(s′0,wx)=v′, λ(s0,wx)=λ(s′0,wx), but λ(s0,wxp)≠λ(s′0,wxp), where |wxp|≤d+1+k, which completes the proof.

We show that this estimate distances is achievable.

The figure 1 shows an initial autonomous state machine А. Let the state machine А′ is the result of a transfer of the arc in the state machine А: the arc (6, 0, 2, 5)is being transferred to state 3 and replaced by the arc (6′,0,2,3′).Because the arc, emanating from the state 6, is being transferred, the shortest word w has length d = 3. It is easy to see that λ(s0,0000)=λ(s′0,0000), but λ(s0,00000)≠λ(s′0,00000). Therefore, p = 00000 and |p| = 5. ρ(A, A′)=1/5. This example shows, that as a result of transferring the arc state machine А′ was to bring state machine, before the states 5 and 6 became equivalent.

Example of a transferring the arc in the state machine DD–2

Figure 1 – Example of a transferring the arc in the state machine DD–2

Now we consider DD–3 state machine B (Fig. 2). Let the state machine B′ is the result of a transfer of the arc in the state machine B: the arc(5,1,0,2)is being transferred into the state 4 and is replaced the arc (5′,1,0,4′). Because, the arc, emanating from state 5, is being transferred, the shortest word w has length d = 3. It is easy to see, that λ(s0,0001)=λ(s′0,0001), but λ(s0,00011)≠λ(s′0,00011). Therefore, p = 00011 and |p| = 5. Hence, ρ(B, B′)=1/5. This example shows, that as a result of transferring the arc, the state machine B′ was remained DD–3.

Example of a transferring the arc in the state machine DD–3.

Figure 2 – Example of a transferring the arc in the state machine DD–3.

( animation: 10 frames, size – 550х350, 146 kilobyte)

(p – distinguish word, |p| – length distinguish words, ρ(A, A′) – measure of closeness)

Directly the Theorem 1 implies the following statement that describes the structure of the class К(А). Let А′ is the result of transfer of the arc (t,x,y,u) in the state of v and d is length of the shortest input word w, for which δ(s0,w)=t. Let also c is length of the shortest word that differentiates the states u and v. Then the following Theorem is true.

Theorem 2. Class Ki(A)consists of all those state machines А′, which are satisfying the following condition: d+с+1=i.

Conclusion

The following results were obtained in the work:

  1. The closeness measure between an etalon, which is an initial DD–k–machine, and the machine, derived from the etalon by transferring one arc, was found.
  2. The upper estimate of specified closeness measure has been found and it was shown that it is achievable.
  3. Class structure state machine with a given closeness of their behavior concerning to the etalon has been described

This description of classes structure can be used as the basis of the algorithm for constructing them.

The master's work is not completed yet. Final completion is on December 2014. Full work text and subject materials can be obtained from the author or her adviser after this date.

References

  1. Кудрявцев В.Б., Грунский И.С., Козловский В.А. Анализ поведения автоматов // Дискретная математика. – 2009. – 21, №1. – С. 3–35.
  2. Bhattacharyya A. Checking experiments on sequential machines. – New York: J. Wiley and Sons, 1989. – 155 с.
  3. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. – 272 с.
  4. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. – М.:Наука, 1985. – 320 с.
  5. Грунский И.С., Козловский В.А., Пономаренко Г.Г., Представления конечных автоматов фрагментами поведения. – К.:Наукова думка, 1990. – 229 с.
  6. Козловский В.А. О структуре контрольных экспериментов с автоматом // Кибер нетика. – 1978. – № 3. – С. 19–33.
  7. Грунский И.С., Копытова О.М. О структуре контрольного эксперимента для определенно–диагностируемого автомата // Теория управляющих систем. – К.: Наук.думка, 1987. – С. 40–54.
  8. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг // Труды VIII Международной конференции "Дискретные модели в теории управляющих систем". – М.: Макс–Пресс, 2009, C. 155–159.
  9. Копытова О.М. Устойчивость автоматов к неисправностям их функции переходов // Труды ИПММ АН Украины. – 2010. – № 21. – С. 57–66.
  10. Бурлаева Е.И., Копытова О.М. Об одном типе локальных преобразований автомата // Материалы IV всеукраинской научно–технической конфиренции студентов, аспирантов и молодых ученых Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013) (24.04–25.04.2013). Донецк: ДонНТУ, 2013. – C. 479–484.
  11. Копытова О.М. О возможности сохранения поведения автомата при перебросках дуг // Материалы VI Международной научно–практической конференции Новости научной мысли – 2010 (27.10–05.11.2010), Чехия. Прага. Издательский дом Образование и наука, 2010 – C. 41–46.
  12. Капитонова Ю.В., Кривий С.Л., Летичевский А.А., Луцкий Г.М., Печурин Н.К. Основы дискретной математики. – К.: Наукова думка, 2002. – 568 с.
  13. Кудявцев В.Б., Грунский И.С., Козловский В.А. Анализ и синтез абстрактных автоматов //Фундаментальная и прикладная математика. – Т. 15, № 4. – 2009. – С. 101–175.