Preview

Математика и математическое моделирование

Расширенный поиск

Особенности процедуры детерминизации конечных автоматов

https://doi.org/10.24108/mathm.0417.0000067

Полный текст:

Аннотация

Конечные автоматы широко используются в теории формальных языков, при реализации автоматного подхода к программированию, а также при синтезе алгоритмов логического управления. Для обеспечения однозначности работы алгоритмов синтезированные конечные автоматы должны быть детерминированными. В рамках подхода к синтезу управлений мобильными роботами, например, основанному на применении теории формальных языков, возникают задачи построения различных конечных автоматов, однако такие конечные автоматы, как правило, не будут детерминированными. Алгоритм детерминизации может быть применен к конечным автоматам, заданным различными способами. Наиболее просто основные идеи алгоритма детерминизации можно объяснить, используя представления конечного автомата в виде взвешенного ориентированного графа.

В работе рассматриваются конечные автоматы, представленные как взвешенные ориентированные графы, и подробно разбирается процедура детерминизации конечных автоматов, представленных указанным образом. Приведено подробное изложение алгоритма детерминизации конечных автоматов. Работа алгоритма детерминизации проиллюстрирована большим количеством примеров.

Об авторах

М. С. Виноградова
МГТУ им. Н. Э .Баумана, Москва
Россия

Виноградова Марина Станиславовна

кафедра ФН12



С. Б. Ткачев
МГТУ им. Н. Э .Баумана, Москва
Россия

Ткачев Сергей Борисович

кафедра ФН12



И. Е. Кандаурова
МГТУ им. Н. Э .Баумана, Москва
Россия

Кандаурова Ирина Евгеньевна

кафедра ФН12



Список литературы

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.


Для цитирования:


Виноградова М.С., Ткачев С.Б., Кандаурова И.Е. Особенности процедуры детерминизации конечных автоматов. Математика и математическое моделирование. 2017;(4):1-17. https://doi.org/10.24108/mathm.0417.0000067

For citation:


Vinogradova M.S., Tkachev S.B., Kandaurova I.E. The Determining Finite Automata Process. Mathematics and Mathematical Modeling. 2017;(4):1-17. (In Russ.) https://doi.org/10.24108/mathm.0417.0000067

Просмотров: 249


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)