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

Abstract

Content

Introduction

The finite state machines (SCs) are of interest for research and practical application. In plain language, & ndash; this is some kind of abstract model, a finite number of states. This model is designed to describe and analyze various processes of discrete action or the flow of discrete information processing processes, for modeling and building devices and processes [1]. In turn, these devices and processes can undergo changes due to external factors. In a number of cases, such an effect leads to a change in the behavior of the automaton. Such changes can be considered as a process of transferring arcs in an automaton. Practical value will be represented by transfers, in which the behavior of the machine will be preserved. In the case of automata-recognizers, these are automata that take the same language as the original automaton after carrying out a series of transformations. In this paper we will consider the possibility of transferring arcs in an acceptor automaton while preserving its behavior.

1. Theme urgency

The universality of the theory of automata allows us to consider different objects from a single point of view, take into account the connections and analogies between them, transfer results from one area to another [1].

The finite state machines have a wide range of uses. The theory of automata is used in computer games when writing artificial intelligence for a character [2]. Machines are used in the systems of preparation and editing of texts [3], in the development of control software systems [4], while programming mobile devices [5], for testing software solutions [6].

Finite automata are widely used in cryptography: in the construction of cryptosystems and as components of cryptalgorithms [7]. In particular, SCs are used in stream and automatic cipher systems, in symmetric ciphers and cryptosystems with public key [8].

Thus, the study of automata is an actual task and can subsequently find wide application in various fields.

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

The object of research is the behavior of the reduced recognition machine when moving arcs.

The subject of the study is the finding of conditions under which the automaton after the transfer of k arcs takes the same language as the original one – automatic machine.

Purpose: development and research of the method of analysis of automata-recognizers, generated by local transformations of the standard.

The main objectives of the study:

  1. Carry out an analysis of the behavior of the recognizer machine when transferring k arcs, k ≥ 1.
  2. Systematize the results obtained in the solution of practical examples.
  3. Find the regularities in which it is possible or not possible to transfer arrows k with the preservation of the behavior of the machine.
  4. Draw conclusions and describe a class of automata that allow the transfer of arcs with preservation of equivalence.

3. Review of research and development

3.1 Overview of international sources

Analysis and study of the structure of automata with similar behavior are very common phenomena, and have been conducted for a long time. These problems relate to the experimental theory with automata, which is carefully described in the book by A. Gill Introduction to the theory of finite automata [9].

The main provisions of the theory of experiments on automata were described by Edward Moore [10]. He made a great contribution to the development of methods for studying spacecraft, first proposing an algorithm for recognizing equivalent automata.

In particular, the theory of experiments is covered by the works of R. Brouwer [11], P. Stark [12], F. Henni [13] and many other authors.

3.2 Overview of national sources

At the national level, the study of automata and their behavior by experiments was considered by M.P. Vasilevskii [14], N.V. Evtushenko, A.F. Petrenko [15-18], V.B. Kudryavtsev, I.S. Grunsky, V. A. Kozlovsky [19-28], V.A. Buevich, N.G. Kalandarashvili, A.A. Tal' [29, 30].

The above works cover three main stages in the study of spacecraft behavior: complexity, combinatorial and characterization.

3.3 Overview of local sources

The investigation of the behavior of automata during the transfer on a local level was carried out by O.M. Kopytova [31-33], and also O.S.Shvets [34] and E.I. Burlaeva [35] as part of the master's work.

For reduced Mealy automata following results were obtained:

4. Machine model

In this paper we consider a recognizer automaton. This is a machine that allows you to determine whether a string of characters belongs to a language. The task of the recognizer is to give an answer, based on the source string, whether it belongs to the specified language or not.

We will consider the cast deterministic acceptor.

We will analyze transfering of arcs in the automatic machine in stages:

5. Theoretical results

Theorem 1. The transfer of one arc in the reduced automaton-discriminator leads to a nonisomorphic automaton.

Theorem 2. For anyone k ≥ 3 there is an automatic recognizer that allows the transfer k-arcs.

Evidence. We construct the reduced acceptor containing n > 3 states, with one input and one final state. By one, each state passes into itself. By zero – goes into state i + 1. First state – input, n-state – final (By one state passes into itself).

In picture 1, the presented automatic recognition machine.

Общий вид акцептора

Picture 1 – General view of the acceptor

Let us show that the automaton is reduced. Take two states i и j, where n – 1 > i ≥ 1, n ≥ j ≥ 1, j > i. It can be seen from the construction that δ (j, 0n-j) ∈ F, а δ (i, 0n-i) ∉ F. States n и n – 1 are distinguishable by one: δ (n, 1) ∈ F, а δ (n – 1, 1) ∉ F.

Transfer k-arcs is carried out as follows:

For clarity, we give the result of the transfer k-arcs in the acceptor (picture 2).

Machine-recognizer after transfer

Picture 2 – Machine-recognizer after transfer

It can be seen from picture 2 that the result is an automaton equivalent to the original one.

Picture 3 illustrates an example of transferring 3 arcs while preserving the equivalence of the automaton.

An example of transferring 3 arcs in an acceptor

Picture 3 – An example of transferring 3 arcs in an acceptor
(animation: 18 frames, 3 cycles of repetition, 134 kilobytes)
(the word 00100 is input, red is the process of recognizing the word automatically, blue – arc transfer process)

Conclusions

Based on the findings, the following conclusions were drawn:

When writing this abstract, the master's work is not yet complete. Final completion: May 2018. The full text of the work and materials on the topic can be obtained from the author or his supervisor after the specified date.

References

  1. Паулин О.Н. Основы теории алгоритмов: учебное пособие / О.Н. Паулин. – Одесса: Автограф, 2005. – 188 с.
  2. Алимов А.А., Шабалина О.А. Искусственный интеллект в компьютерных играх. Многоуровневое планирование и реактивное поведение агентовагентов / А.А. Алимов, О.А. Шабалина // Известия ВолгГТУ. – 2011. – № 10. – С. 90-94.
  3. Капитонова Ю.В. Основы дискретной математики / Ю.В. Капитонова, С.Л. Кривий, А.А. Летичевский, Г.М. Луцкий, Н.К. Печурин. – К.: Наукова думка, 2002. – 568 с.
  4. Смирнова Н.В., Смирнов В.В. Применение теории конечных автоматов в разработке программных систем / Н.В. Смирнова, В.В., Смирнов // Збірник наукових праць Кіровоградського національного технічного університету. Техніка в сільськогосподарському виробництві, галузеве машинобудування, автоматизація. – 2014. – Вип. 27. – С. 316-320.
  5. Салмре И. Программирование мобильных устройств на платформе .Net Compact Framework / И. Салмре. – М.: Вильямс, 2006. – 702 с.
  6. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Использование конечных автоматов для тестирования программ / И.Б. Бурдонов, А.С. Косачев, В.В Кулямин // Программирование. – 2000. – № 2. – С. 12-28.
  7. Фомичев В.М. Дискретная математика и криптология / В.М. Фомичев. – М.: ДИАЛОГ-МИФИ, 2003. – 400 с.
  8. Агибалов Г.П. Конечные автоматы в криптографии / Г.П. Агибалов // Прикладная дискретная математика. Приложение. – 2009. – № 2. – С. 43-73.
  9. Гилл А. Введение в теорию конечных автоматов / А. Гилл. – М.: Наука, 1966. – 272 с.
  10. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами / Э.Ф. Мур // Автоматы. – М.: Иностр. лит. – 1956. – С. 179-210.
  11. Брауэр Р. Введение в теорию конечных автоматов/ Р. Брауэр. – М.: Радио и связь, 1987. – 392 с.
  12. Starke P. Abstract automata / P. Stapke // American Elsevier, 1972. – 419 с.
  13. Hennie F.C. Fault detecting experiments for sequential circuits / F.C. Hennie // Proc. 5 Annual Symp. «Switch. Circuits Th. and Logic. Design». – 1964. – P. 95-110.
  14. Василевский М.П. О распознавании неисправностей автомата / М.П. Василевский // Кибернетика. – 1973. – № 4. – С. 93-108.
  15. Евтушенко Н.В., Лебедев А.В., Петренко А. Ф. О проверяющих экспериментах с недетерминированными автоматами / Н.В. Евтушенко, А.В. Лебедев, А.Ф. Петренко // Автоматика и вычислительная техника. – 1991. – № 6. – С. 81-85.
  16. Евтушенко Н.В., Петренко А.Ф. Метод построения проверяющих экспериментов для произвольного недетерминированного автомата / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1990. – № 5. – С. 73-76.
  17. Евтушенко Н.В., Петренко А.Ф. О проверяющих возможностях кратных экспериментов / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1989. – №3. – С. 9-14.
  18. Петренко А.Ф. Эксперименты над протокольными объектами / А.Ф. Петренко // Автоматика и вычислительная техника. – 1987. – № 1. – С. 16-21.
  19. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов/ В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. – М.: Наука, 1985. – 320 с.
  20. Кудрявцев В.Б., Грунский И.С., Козловский В.А. Анализ поведения автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский // Дискретная математика. – 2009. – №1. – С. 3-35.
  21. Кудявцев В.Б., Грунский И.С., Козловский В.А. Анализ и синтез абстрактных автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский //Фундаментальная и прикладная математика. – Т. 15, № 4. – 2009. – С. 101-175.
  22. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представления конечных автоматов фрагментами поведения/ И.С. Грунский, В.А. Козловский, Г.Г. Пономаренко. – Киев: Наукова думка, 1990. – 232 с.
  23. Грунский И.С. Анализ поведения конечных автоматов/ И.С. Грунский. – Луганск: изд-во Луганск. гос. пед. ун-та, 2003. – 318 с.
  24. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов/ И.С. Грунский, В.А. Козловский. – Киев: Наукова думка, 2004. – 246 с.
  25. Грунский И.С., Максименко И.И. Об экспериментах с автоматами при отсутствии верхней оценки числа состояний / И.С. Грунский, И.И. Максименко // Кибернетика и системный анализ. – 1999. – № 4. – С. 59-71.
  26. Козловский В.А. О структуре контрольных экспериментов с автоматом / В.А. Козловский // Кибернетика. – 1978. – № 3. – С. 19-33.
  27. Козловский В.А. О распознавании автомата относительно локально порожденного класса / В.А. Козловский // ДАН СССР. – 1981. – № 5. – С. 1047-1049.
  28. Козловский В.А., Копытова О.М. Представления автоматов относительно m-плотных классов / В.А. Козловский, О.М. Копытова // Матер. VIII Межд. семинара «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.) – М.: Изд. МГУ. – С. 277-280.
  29. Буевич В.А., Каландарашвили Н.Г., Таль А.А. Об описании конечного автомата с помощью конечного множества вход-выходных слов / В.А. Буевич, Н.Г. Каландарашвили, А.А. Таль // Автоматика и телемеханика. 1970. – № 1. – С. 112-122.
  30. Буевич В.А., Каландарашвили Н.Г., Таль А.А. Конечные автоматы – эквивалентность и поведение/ В.А. Буевич, Н.Г. Каландарашвили, А.А. Таль. – М.: Наука, 1984. – 192 с.
  31. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг / О.М. Копытова // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем». – М.: Макс-Пресс, 2009. – C. 155-159.
  32. Копытова О.М. О возможности сохранения поведения автомата при перебросках дуг / О.М. Копытова // Материалы VI Международной научно–практической конференции Новости научной мысли – 2010 (27.10-05.11.2010), Чехия. Прага. Издательский дом Образование и наука, 2010 – C. 41-46.
  33. Копытова О.М. Устойчивость автоматов к неисправностям их функции переходов / О.М. Копытова // Труды ИПММ АН Украины. – 2010. – № 21. – С. 57-66.
  34. Швец О.С., Копытова О.М. О сравнении поведения ОДk-эталона и автоматов, порождаемых его локальными преобразованиями / О.С. Швец, О.М. Копытова // Материалы V всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2014)» (22.04-23.04.2014). Донецк: ДонНТУ, 2014. – С. 365-369.
  35. Бурлаева Е.И., Копытова О.М. Об одном типе локальных преобразований автомата / Е.И. Бурлаева, О.М. Копытова // Материалы IV всеукраинской научно-технической конфиренции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013)» (24.04-25.04.2013). Донецк: ДонНТУ, 2013. – C. 479-484.