Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Построение контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью

# 07, июль 2014
DOI: 10.7463/0714.0717777
Файл статьи: S&E-BMST...o142.pdf (343.04Кб)
авторы: Белоусов А. И., Ткачев С. Б.

УДК 519.76

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


Статья посвящена разработке алгоритма построения контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью (МП-автомата).
Разработка алгоритма основана на представлении МП-автомата в виде ориентированного мультиграфа. Такой подход позволяет оптимизировать констекстно-свободную (КС-) грамматику, которая строится по известному алгоритму по системе команд МП-автомата.
Алгоритм построения оптимизированной КС-грамматики основан на перечислении определенных путей в мультиграфе. Методом, аналогичным стандартному поиску в глубину в ориентированном графе, перечисляются так называемые сбалансированные пути, прохождение по которым соответствует чтению входного слова МП-автоматом, пока он проходит последовательность состояний от начального до заключительного с опустошением магазина, допуская тем самым входное слово. Это позволяет освободить КС-грамматику, эквивалентную данному МП-автомату, от бесполезных нетерминалов и обеспечить порождение всех цепочек, допускаемых МП-автоматом. Таким образом, КС-грамматика, которую строит  алгоритм, породит именно тот язык, который допускается МП-автоматом. Кроме того, представленный в статье алгоритм может выступать в роли порождающей модели языка, допускаемого МП-автоматом. 
Основной результат статьи состоит в разработке алгоритма построения оптимизированной КС-грамматики по мультиграфу МП-автомата. Дается описание алгоритма в псевдокоде и вычисляется верхняя оценка сложности, составляющей величину порядка куба числа дуг мультиграфа.
Мультиграфы МП-автоматов рассматривались в ряде работ. Но, в основном, в этих работах мультиграфы используются исключительно как иллюстрация. В этой же статье (как в статье авторов, продолжением которой служит данная), мультиграф используется не только как наглядное представление МП-автомата, но как рабочая модель, в терминах которой определяется язык МП-автомата и доказывается эквивалентность такой модели известным.
Таким образом, в статье предложен эффективный алгоритм перечисления путей в ориентированном мультиграфе, на основе которого удается построить оптимизированную КС-грамматику, эквивалентную исходному МП-автомату.
Среди задач, решение которых продолжит начатое исследование, нахождение более точной верхней оценки сложности разработанного алгоритма.

Список литературы
  1. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. 744 с.
  2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2 т. Т.1: пер. с англ. М.: Мир, 1978. 612 с.
  3. КрищенкоB.A. Использование LR таблиц для разбора естественного языка // Исследовано в России: электрон. журнал. 2000. Т. 3. С. 948-945. Режим доступа:http://zhurnal.ape.relarn.ru/articles/2000/067.pdf (дата обращения 25.06.2014).
  4. Dantam N., Stilman M. The Motion Grammar: Analysis of a Linguistic Method for Robot Control // IEEE Transactions on Robotics. 2013. Vol. 29, no. 3. P. 704-718. DOI: 10.1109/TRO.2013.2239553
  5. 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. P. 1077-01091. DOI: 10.1109/TRO.2005.852260
  6. Белоусов А.И., Ткачев С.Б. Мультиграфовое представление автоматов с магазинной памятью //Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 9. DOI: 10.7463/0912.0460973
  7. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. 247 с.



Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА
18.12.2017
С 21 по 24 ноября 2017г. в МГТУ им. Н.Э. Баумана прошла XII Всероссийская инновационная молодежная научно-инженерная выставка «Политехника», посвященная 170-летию со дня рождения Н.Е. Жуковского в рамках Всероссийского инновационного молодежного научно-инженерного форума «Политехника».

11.10.2017
XII Всероссийская инновационная молодежная научно-инженерная выставка «ПОЛИТЕХНИКА», посвященная 170-летию со дня рождения Н.Е. Жуковского 21–24 ноября 2017 года г. Москва

25.05.2017
C 15 по 17 мая 2017г. в МГТУ им. Н.Э. Баумана прошел III этап (Всероссийский) Всероссийской студенческой олимпиады по физике (в технических вузах).

25.04.2017
С 12 по 14 апреля в МГТУ им. Н.Э. Баумана прошел Всероссийский этап Всероссийской олимпиады по безопасности жизнедеятельности.

4.04.2017
С 14 по 16 марта 2017г. в МГТУ им. Н.Э. Баумана прошел III (Всероссийский) тур Всероссийской студенческой олимпиады по иностранному языку (английский в технических вузах).




Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2018 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)