Другие журналы
научное издание МГТУ им. Н.Э. Баумана
НАУКА и ОБРАЗОВАНИЕ
Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
Построение контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью
# 07, июль 2014
DOI: 10.7463/0714.0717777
Файл статьи:
S&E-BMST...o142.pdf
(343.04Кб)
S&E-BMST...o142.pdf
(343.04Кб)
| УДК 519.76 | Россия, МГТУ им. Н.Э. Баумана  |
Статья посвящена разработке алгоритма построения контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью (МП-автомата).
Разработка алгоритма основана на представлении МП-автомата в виде ориентированного мультиграфа. Такой подход позволяет оптимизировать констекстно-свободную (КС-) грамматику, которая строится по известному алгоритму по системе команд МП-автомата.
Алгоритм построения оптимизированной КС-грамматики основан на перечислении определенных путей в мультиграфе. Методом, аналогичным стандартному поиску в глубину в ориентированном графе, перечисляются так называемые сбалансированные пути, прохождение по которым соответствует чтению входного слова МП-автоматом, пока он проходит последовательность состояний от начального до заключительного с опустошением магазина, допуская тем самым входное слово. Это позволяет освободить КС-грамматику, эквивалентную данному МП-автомату, от бесполезных нетерминалов и обеспечить порождение всех цепочек, допускаемых МП-автоматом. Таким образом, КС-грамматика, которую строит алгоритм, породит именно тот язык, который допускается МП-автоматом. Кроме того, представленный в статье алгоритм может выступать в роли порождающей модели языка, допускаемого МП-автоматом.
Основной результат статьи состоит в разработке алгоритма построения оптимизированной КС-грамматики по мультиграфу МП-автомата. Дается описание алгоритма в псевдокоде и вычисляется верхняя оценка сложности, составляющей величину порядка куба числа дуг мультиграфа.
Мультиграфы МП-автоматов рассматривались в ряде работ. Но, в основном, в этих работах мультиграфы используются исключительно как иллюстрация. В этой же статье (как в статье авторов, продолжением которой служит данная), мультиграф используется не только как наглядное представление МП-автомата, но как рабочая модель, в терминах которой определяется язык МП-автомата и доказывается эквивалентность такой модели известным.
Таким образом, в статье предложен эффективный алгоритм перечисления путей в ориентированном мультиграфе, на основе которого удается построить оптимизированную КС-грамматику, эквивалентную исходному МП-автомату.
Среди задач, решение которых продолжит начатое исследование, нахождение более точной верхней оценки сложности разработанного алгоритма.
Список литературы
- Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. 744 с.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2 т. Т.1: пер. с англ. М.: Мир, 1978. 612 с.
- КрищенкоB.A. Использование LR таблиц для разбора естественного языка // Исследовано в России: электрон. журнал. 2000. Т. 3. С. 948-945. Режим доступа:http://zhurnal.ape.relarn.ru/articles/2000/067.pdf (дата обращения 25.06.2014).
- 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
- 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
- Белоусов А.И., Ткачев С.Б. Мультиграфовое представление автоматов с магазинной памятью //Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 9. DOI: 10.7463/0912.0460973
- Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. 247 с.
Публикации с ключевыми словами: автомат с магазинной памятью, МП-автомат, ориентированный мультиграф, контекстно-свободная грамматика, КС-грамматика, сбалансированный путь, поиск в глубину
Публикации со словами: автомат с магазинной памятью, МП-автомат, ориентированный мультиграф, контекстно-свободная грамматика, КС-грамматика, сбалансированный путь, поиск в глубину
Смотри также:
Тематические рубрики:
Поделиться:
| Авторы |
| Пресс-релизы |
| Библиотека |
| Конференции |
| Выставки |
| О проекте |
| Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00) |
|
 |
|||
| © 2003-2024 «Наука и образование» Перепечатка материалов журнала без согласования с редакцией запрещена Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00) | |||||
