Математика и математическое моделирование. 2017; : 1-17
Особенности процедуры детерминизации конечных автоматов
https://doi.org/10.24108/mathm.0417.0000067Аннотация
Конечные автоматы широко используются в теории формальных языков, при реализации автоматного подхода к программированию, а также при синтезе алгоритмов логического управления. Для обеспечения однозначности работы алгоритмов синтезированные конечные автоматы должны быть детерминированными. В рамках подхода к синтезу управлений мобильными роботами, например, основанному на применении теории формальных языков, возникают задачи построения различных конечных автоматов, однако такие конечные автоматы, как правило, не будут детерминированными. Алгоритм детерминизации может быть применен к конечным автоматам, заданным различными способами. Наиболее просто основные идеи алгоритма детерминизации можно объяснить, используя представления конечного автомата в виде взвешенного ориентированного графа.
В работе рассматриваются конечные автоматы, представленные как взвешенные ориентированные графы, и подробно разбирается процедура детерминизации конечных автоматов, представленных указанным образом. Приведено подробное изложение алгоритма детерминизации конечных автоматов. Работа алгоритма детерминизации проиллюстрирована большим количеством примеров.
Список литературы
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: учеб. для вузов / Под ред. В.С. Зарубина и А.П. Крищенко. 5-е изд. М.: Изд-во МГТУ им. Н.Э. Баумана, 2015. 743 с.
2. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е изд. М.: Вильямс, 2002. 527 с. [Hopcroft J.E., Motwani R., Ullman J.D. Introduction to automata theory, languages and computation. 2nd ed. Boston: Addison-Wesley, 2001. 521 p.].
3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2 т. Т.1. М.: Мир, 1978. 612 с. [Aho A.V., Ullman J.D. The theory of parsing, translation and compiling. Vol. 1. Englewood Cliffs: Prentice-Hall, 1972].
4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с. [Aho A.V., Hopcroft J.E., Ullman J.D. The design and analysis of computer algorithms. Reading: Addison-Wesley, 1974. 470 p.].
5. Новорусский В.В. Конечноавтоматные системы управления (принципы построения и анализ поведения). Новосиб.: Наука, 1982. 269 с.
6. Dantam N., Stilman M. The motion grammar: Analysis of a linguistic method for robot control // IEEE Transactions on Robotics. 2013. Vol. 29. No. 3. Pp. 704-718. DOI: 10.1109/TRO.2013.2239553
7. Frazzoli E., Dahleh M.A, Feron E. Maneuver-based motion planning for nonlinear systems with symmetries // IEEE Transactions on Robotics. 2005. Vol. 21. No. 6. Pp. 1077-1091. DOI: 10.1109/TRO.2005.852260
8. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Известия РАН. Теория и системы управления. 2000. № 6. C. 63-81.
9. Шалыто А.А. Алгоритмизация и программирование для систем логического управления и "реактивных" систем // Автоматика и телемеханика. 2001. № 1. C. 3-39.
10. Максимов А.А. Один подход к построению конечноавтоматной управляющей сети // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2012. Спец. вып. 6: Робототехнические системы. С. 14-29.
11. Kobele G.M., Riggle J., Brooks R., Friedlander D., Taylor C., Stabler E. Induction of prototypes in a robotic setting using local search MDL // 9th Intern. Symp. on artificial life and robotics: AROB’2004 (Beppu, Oita, Japan, January 28-30, 2004): Proc. 2004. Pp. 482-485.
12. Горячкин Б.С. Развитие теории конечных автоматов и ее приложений в МГТУ им. Н.Э. Баумана // Инженерный вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 4. С. 538-542. Режим доступа: http://engbul.bmstu.ru/doc/730377.html (дата обращения 19.08.2017).
13. Brockett R.W. Formal languages for motion description and map making // Robotics. Providence: Amer. Math. Soc., 1990. Pp. 181–193.
Mathematics and Mathematical Modeling. 2017; : 1-17
The Determining Finite Automata Process
https://doi.org/10.24108/mathm.0417.0000067Abstract
The theory of formal languages widely uses finite state automata both in implementation of automata-based approach to programming, and in synthesis of logical control algorithms.
To ensure unambiguous operation of the algorithms, the synthesized finite state automata must be deterministic. Within the approach to the synthesis of the mobile robot controls, for example, based on the theory of formal languages, there are problems concerning the construction of various finite automata, but such finite automata, as a rule, will not be deterministic. The algorithm of determinization can be applied to the finite automata, as specified, in various ways. The basic ideas of the algorithm of determinization can be most simply explained using the representations of a finite automaton in the form of a weighted directed graph.
The paper deals with finite automata represented as weighted directed graphs, and discusses in detail the procedure for determining the finite automata represented in this way. Gives a detailed description of the algorithm for determining finite automata. A large number of examples illustrate a capability of the determinization algorithm.
References
1. Belousov A.I., Tkachev S.B. Diskretnaya matematika: ucheb. dlya vuzov / Pod red. V.S. Zarubina i A.P. Krishchenko. 5-e izd. M.: Izd-vo MGTU im. N.E. Baumana, 2015. 743 s.
2. Khopkroft Dzh., Motvani R., Ul'man Dzh. Vvedenie v teoriyu avtomatov, yazykov i vychislenii. 2-e izd. M.: Vil'yams, 2002. 527 s. [Hopcroft J.E., Motwani R., Ullman J.D. Introduction to automata theory, languages and computation. 2nd ed. Boston: Addison-Wesley, 2001. 521 p.].
3. Akho A., Ul'man Dzh. Teoriya sintaksicheskogo analiza, perevoda i kompilyatsii. V 2 t. T.1. M.: Mir, 1978. 612 s. [Aho A.V., Ullman J.D. The theory of parsing, translation and compiling. Vol. 1. Englewood Cliffs: Prentice-Hall, 1972].
4. Akho A., Khopkroft Dzh., Ul'man Dzh. Postroenie i analiz vychislitel'nykh algoritmov. M.: Mir, 1979. 536 s. [Aho A.V., Hopcroft J.E., Ullman J.D. The design and analysis of computer algorithms. Reading: Addison-Wesley, 1974. 470 p.].
5. Novorusskii V.V. Konechnoavtomatnye sistemy upravleniya (printsipy postroeniya i analiz povedeniya). Novosib.: Nauka, 1982. 269 s.
6. Dantam N., Stilman M. The motion grammar: Analysis of a linguistic method for robot control // IEEE Transactions on Robotics. 2013. Vol. 29. No. 3. Pp. 704-718. DOI: 10.1109/TRO.2013.2239553
7. Frazzoli E., Dahleh M.A, Feron E. Maneuver-based motion planning for nonlinear systems with symmetries // IEEE Transactions on Robotics. 2005. Vol. 21. No. 6. Pp. 1077-1091. DOI: 10.1109/TRO.2005.852260
8. Shalyto A.A. Avtomatnoe proektirovanie programm. Algoritmizatsiya i programmirovanie zadach logicheskogo upravleniya // Izvestiya RAN. Teoriya i sistemy upravleniya. 2000. № 6. C. 63-81.
9. Shalyto A.A. Algoritmizatsiya i programmirovanie dlya sistem logicheskogo upravleniya i "reaktivnykh" sistem // Avtomatika i telemekhanika. 2001. № 1. C. 3-39.
10. Maksimov A.A. Odin podkhod k postroeniyu konechnoavtomatnoi upravlyayushchei seti // Vestnik MGTU im. N.E. Baumana. Ser. Priborostroenie. 2012. Spets. vyp. 6: Robototekhnicheskie sistemy. S. 14-29.
11. Kobele G.M., Riggle J., Brooks R., Friedlander D., Taylor C., Stabler E. Induction of prototypes in a robotic setting using local search MDL // 9th Intern. Symp. on artificial life and robotics: AROB’2004 (Beppu, Oita, Japan, January 28-30, 2004): Proc. 2004. Pp. 482-485.
12. Goryachkin B.S. Razvitie teorii konechnykh avtomatov i ee prilozhenii v MGTU im. N.E. Baumana // Inzhenernyi vestnik. MGTU im. N.E. Baumana. Elektron. zhurn. 2015. № 4. S. 538-542. Rezhim dostupa: http://engbul.bmstu.ru/doc/730377.html (data obrashcheniya 19.08.2017).
13. Brockett R.W. Formal languages for motion description and map making // Robotics. Providence: Amer. Math. Soc., 1990. Pp. 181–193.
