Белгород, Белгородская область, Россия
В статье рассматривается задача сокращения количества состояний распознавателя с магазинной памятью за счет исключения лишних переходов, которые никогда не срабатывают, и исключения лишних состояний, в которых не может оказаться распознаватель в процессе обработки допустимой цепочки. Предлагается алгоритм поиска лишних переходов и состояний, основанный на представлении распознавателя в виде графа. Приводится пример распознавателя, в котором предложенный алгоритм устраняет лишние переходы и состояния. Этот алгоритм не гарантирует исключения всех лишних переходов и состояний. Приводится пример распознавателя с лишними переходами и состояниями, которые не обнаруживаются алгоритмом. Предложенный алгоритм может быть использован при разработке программ обработки формальных языков
контекстно-свободный язык, распознаватель с магазинной памятью, состояние, переход, эквивалентные преобразования
1. Schutzenberger M.P. “On context-free languages and pushdown automata”, Information and Control 6:3 (1963), pp. 246 - 264.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т. 1. 612 с.
3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. 656 с.
4. Мартыненко Б.К. Синтаксически управ-ляемая обработка данных. Изд. 2-е, дополн. СПб: Изд-во С.-Петербургского университета, 2004 г. 317 с.
5. Ахо А, Лам М., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и ин-струментарий. М: Издательский дом “Вильямс”, 2008. 1185 с.
6. Hopcroft J.E., Motwani R., J.D. Ullman J.D. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson., 2013. p. 496.
7. Белоусов А.И., Ткачев С.Б. Мультигра-фовое представление автоматов с магазинной памятью // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2012. № 9. С. 11.
8. Станевичене Л.И. Графы магазинных автоматов // Учредительная конф. Российской ассоциации "Женщины-математики". Тез. докл. М. 1993(а). С. 50
9. Вылиток А.А. О построении графа магазинного автомата // Вестн. Моск. ун-та. Сер. 15. 1996. № 3. С. 68 - 73.
10. Брауэр В. Введение в теорию конечных автоматов М.: Книга по Требованию, 2012. С. 272.
11. Рязанов Ю. Д. Синтез распознавателей с магазинной памятью по детерминированным синтаксическим диаграммам // Вестник ВГУ. Системный анализ и информационные технологии. 2014. №1. С. 138-145.
12. Рязанов Ю. Д., Савёлова И. Н. Преобразование распознавателя с магазинной памятью и одним состоянием в распознаватель с конечным множеством состояний // Моделирование, оптимизация и информационные технологии. 2015. № 4 (11). С. 13.
13. Polyakov V.M., Ryazanov Y.D. Virt Charts to Multiport Component Syntactic Charts Transformation // Global Journal of Pure and Applied Mathematics. 2015. Т. 11. № 5. С. 3939-3952.
