ГлавнаяАрхивМинимизация контекстно-свободных грамматик

Минимизация контекстно-свободных грамматик | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/10

Решается задача преобразования исходной контекстно-свободной грамматики (КС-грамматики) без лишних символов в эквивалентную ей грамматику меньшей сложности. Предлагается способ минимизации КС-грамматики, основанный на введённом отношении на множестве нетерминалов, обладающим свойством эквивалентности. Это отношение разбивает множество нетерминалов на классы эквивалентности, и новая КС-грамматика строится на нетерминалах, являющихся представителями классов эквивалентности. В результате получается КС-грамматика с меньшим количеством нетерминалов и правил.
  • Title Минимизация контекстно-свободных грамматик
  • Headline Минимизация контекстно-свободных грамматик
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 45
  • Date:
  • DOI 10.17223/20710410/45/10
Ключевые слова
формальный язык, формальная грамматика, отношение эквивалентности, минимизация, formal language, formal grammar, equivalence relation, minimization
Авторы
Ссылки
Aho A. V. and Ullman J. D. The Theory of Parsing, Translation and Compiling. NJ, USA: Prentice-Hall Inc., 1972. V. 1. 560 p
Aho A. V., Lam M. S., Sethi R., and Ullman J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 2007, 1009 p
Конюхова О. В., Кравцова Э. А. Программная реализация алгоритмов упрощения контекстно-свободных грамматик на языках программирования Haskell и Prolog // Информационные системы и технологии. 2017. №4. С. 77-86
Hopcroft J. E. An nlog n algorithm for minimizing states in a finite automaton // Theory of Machines and Computations. N.Y.: Academic Press, 1971. P. 189-196
Hopcroft J. E., Motwani R., and Ullman J. D. Introduction to Automata Theory, Languages, and Computation. Pearson, 2013, 496 p
Мартыненко Б. К. Ещё один метод минимизации конечных автоматов // Компьютерные инструменты в образовании. 2017. № 1. С. 5-14
Polyakov V. M. and Ryazanov Yu. D. Reducing the number of states in pushdown recognizers by means of equivalence relation // Intern. J. Pharmacy & Technology. 2016. V. 8. No. 4. P. 22578-22587
Рязанов Ю. Д. Сокращение количества магазинных символов в распознавателях с магазинной памятью и одним состоянием // Вестник БГТУ им. В. Г. Шухова. 2017. № 6. С. 152-157
Мартыненко Б. К. Синтаксически управляемая обработка данных. СПб.: Изд-во С.-Петербург. ун-та, 2004. 316 c
Федорченко Л. Н. Минимизация трансляционной КСР-грамматики и состояний синтаксического анализатора КСР-языка // Вестник Бурятского государственного университета. Математика, информатика. 2013. № 2. С. 39-49
Стасенко А. П. Автоматная модель визуального описания синтаксического разбора // Вычислительные технологии. 2008. Т. 13. № 5. С. 70-87
Минимизация контекстно-свободных грамматик | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/10
Минимизация контекстно-свободных грамматик | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/10