ИСТИНА

Основополагающая часть теории формальных языков может быть рассмотрена как исследование конечных описаний для бесконечных языков. К классическим описаниям относятся распознающие автоматы и порождающие грамматики. Хорошо известно представление конечного автомата в виде так называемой диаграммы состояний — мультиграфа с помеченными вершинами и дугами. В работах [1, 2] предложено графовое представление бесконтекстных языков, основанное на понятии графа магазинного автомата. В данном докладе рассматривается дальнейшее обобщение, предложенное А.А. Вылитком, позволяющее распространить графовый подход на языки, не являющиеся бесконтекстными (так называемые L-графы). Изучается взаимосвязь между классическими описаниями и графовыми. Предлагаются приемы трансформации графов, позволяющие для некоторых подклассов строить алгоритмы для проверки эквивалентности языковых описаний. Литература 1. Станевичене Л.И. О некоторых определениях класса КС-языков // Программирование, 1999. №5. С.15-25 2. Вылиток А.А. О построении графа магазинного автомата // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 1996 №3 С. 68-73. 3. Вылиток А.А., Сутырин П.Г., Харченков С.Л., Юдочев Д.В. О сопряжениях графовых описаний формальных языков. Программные системы и инструменты. Тематический сборник. Под ред. Л.Н. Королева. – М.: Издательский отдел факультета ВМК МГУ, 2009.