Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
Построение контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью
# 07, июль 2014 DOI: 10.7463/0714.0717777
Файл статьи:
S&E-BMST...o142.pdf
(343.04Кб)
Статья посвящена разработке алгоритма построения контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью (МП-автомата). Разработка алгоритма основана на представлении МП-автомата в виде ориентированного мультиграфа. Такой подход позволяет оптимизировать констекстно-свободную (КС-) грамматику, которая строится по известному алгоритму по системе команд МП-автомата. Алгоритм построения оптимизированной КС-грамматики основан на перечислении определенных путей в мультиграфе. Методом, аналогичным стандартному поиску в глубину в ориентированном графе, перечисляются так называемые сбалансированные пути, прохождение по которым соответствует чтению входного слова МП-автоматом, пока он проходит последовательность состояний от начального до заключительного с опустошением магазина, допуская тем самым входное слово. Это позволяет освободить КС-грамматику, эквивалентную данному МП-автомату, от бесполезных нетерминалов и обеспечить порождение всех цепочек, допускаемых МП-автоматом. Таким образом, КС-грамматика, которую строит алгоритм, породит именно тот язык, который допускается МП-автоматом. Кроме того, представленный в статье алгоритм может выступать в роли порождающей модели языка, допускаемого МП-автоматом. Основной результат статьи состоит в разработке алгоритма построения оптимизированной КС-грамматики по мультиграфу МП-автомата. Дается описание алгоритма в псевдокоде и вычисляется верхняя оценка сложности, составляющей величину порядка куба числа дуг мультиграфа. Мультиграфы МП-автоматов рассматривались в ряде работ. Но, в основном, в этих работах мультиграфы используются исключительно как иллюстрация. В этой же статье (как в статье авторов, продолжением которой служит данная), мультиграф используется не только как наглядное представление МП-автомата, но как рабочая модель, в терминах которой определяется язык МП-автомата и доказывается эквивалентность такой модели известным. Таким образом, в статье предложен эффективный алгоритм перечисления путей в ориентированном мультиграфе, на основе которого удается построить оптимизированную КС-грамматику, эквивалентную исходному МП-автомату. Среди задач, решение которых продолжит начатое исследование, нахождение более точной верхней оценки сложности разработанного алгоритма. Список литературы
Публикации с ключевыми словами: автомат с магазинной памятью, МП-автомат, ориентированный мультиграф, контекстно-свободная грамматика, КС-грамматика, сбалансированный путь, поиск в глубину Публикации со словами: автомат с магазинной памятью, МП-автомат, ориентированный мультиграф, контекстно-свободная грамматика, КС-грамматика, сбалансированный путь, поиск в глубину Смотри также: Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||
|