НАУКА и ОБРАЗОВАНИЕ

УДК 519.76 

Россия, МГТУ им. Баумана

mathmod@bmstu.ru

В статье рассматривается представление автоматов с магазинной памятью (МП-автоматов) в виде ориентированных мультиграфов. Дано определение языка МП-автомата, представленного своим мультиграфом,  и доказана равносильность этого определения с известным. В терминах мультиграфового представления рассмотрены также некоторые свойства МП-автоматов, в частности, доказана регулярность множества всех магазинных цепочек.

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

 1.                Белоусов А.И., Ткачев С.Б. Дискретная математика. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. -744 с. 

2.                Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: пер. с англ. В 2 т. Т. 1. Синтаксический анализ.- М.: Мир, 1978. - 612 с. (Aho A.V., Ullman J.D. The Theory of Parsing, Translation, and Compilin. Vol. 1. Parsing.- Prentice Hall, 1972.).

3.                Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений : пер. с англ.- 2-е изд.- М.: Издательский дом "Вильямс", 2002. - 528 с. (Hopcroft John E., Motwani R., Ullman J.D. Introduction to Automata Theory, Languages, and Computation .- 2nd ed.- Addison-Wesley, 2000.).

4.                Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. - М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006.- 247 с.