Применение итераций конечных языков в алгоритмических задачах теории формальных языков

• Автор: Алексеева, Анна Геннадьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Тольятти
• Количество страниц: 123 с.

Оглавление
Введение

Исторический обзор .

Общая характеристика диссертации .

Структура диссертационной работы

Применяемые обозначения.

1 Итерации языков и конечные автоматы

1.1 Алгоритм генерации специальных морфизмов . .

1.2 Необходимое условие равенства бесконечных итераций

1.3 Алгоритмы генерации дополненных максимальных префиксных кодов

1.4 Итерации языков и конечные автоматы

2 Случай бесконечных итерируемых языков
2.1 Итерации языков как абстрактные семейства . .
2.2 Подмоноиды супермоноида
2.3 Эквивалентность для случая бесконечных итерируемых языков.
3 Модели бесконечных итерируемых языков .
3.1 Специальное описание грамматических структур КСязыков.
3.2 Итерации языков и проблема звездной высоты .
Оглавление
3.3 Алгоритмы специального декодирования.
Заключение
Основные результаты диссертации
Литература


Для описания этих подклассов мы часто рассматриваем пары языков, фактически представляющих собой множества пар скобок. Упомянем ещё некоторые задачи, связанные с описанными выше и рассматривавшиеся в научных работах в последние лет. Это, прежде всего, задачи графического описания магазинных автоматов - []. Описание подклассов класса КС-языков связано с проблемой звёздной высоты (определяемой как для конечных автоматов, так и для регулярных языков); кроме публикаций автора данной диссертации (см. Связаны с описанием подклассов класса КС-языков и некоторые специальные алгебраические структуры; среди множества работ по автоматным алгебрам и т. Как уже было отмечено выше, для всех формализмов, задающих некоторый подкласс класса контекстно-свободных языков, в частности - для каждого из формализмов, упомянутых выше, важен ответ на вопрос - разрешима ли в нём проблема эквивалентности. Положительный ответ на этот вопрос делает рассматриваемый формализм особенно удобным аппаратом для задания КС-языков (либо их подклассов) в системах автоматизации построения компиляторов. Использованные выше термины «класс» и «подкласс» (вместо «множество» и «подмножество» - см. Они часто применяется для того, чтобы подчеркнуть, что рассматриваемое множество обладает некоторыми специальными свойствами. В теории формальных языков часто таким свойством, причём единственным, считается свойство замкнутости рассматриваемого множества языков относительно любых морфизмов3. Для морфизмов мы используем терминологию из книги []. При этом отметим, что в различных областях алгебры термином «морфизм» иногда называют и другие (схожие) понятия. Подробное определение, применяемое нами, см. А если потребовать ещё и замкнутость относительно инверсных морфизмов4 и пересечений с регулярными множествами, то данный класс языков можно назвать полным абстрактным семейством языков ([, , ]). Такими свойствами большинство языков, рассматриваемых в данной диссертации, обладают. Разрешимость проблемы эквивалентности в некотором подклассе класса контекстно-свободных языков делает этот подкласс весьма удобным для конкретного варианта описания языков, в частности - языков программирования и некоторых их грамматических структур. По поводу этого термина нужно отметить следующее. Строгого определение понятия «грамматическая структура», приемлемого для всех возможных практических (в том числе - программистских) приложений, вероятно, привести невозможно - однако это понятие нередко употребляется в научной литературе. При этом часто некоторые пары грамматических структур являются при описании конкретного формального языка аналогами пар скобок- т. Итерация языков и инверсные морфизмы также определены в вышеупомянутой монографии А. Саломаа. Строгие определения приводятся далее. По-видимому, эти примеры можно считать поясняющими все возможные ситуации. Более сложные грамматические структуры (прежде всего -в конкретных языках программирования) нередко определяются как скобочные языки либо как простые скобочные языки -образованные над некоторым множеством пар скобок, заданных каким-либо образом. При этом для реальных грамматических структур конкретных языков программирования такое множество пар скобок обычно является бесконечным. Важно отмстить, что подобные конструкции могут появляться и в двухуровневых грамматиках (в частности, при описании языка Алгол-, [1) - причём принципиально иным способом, чем рассмотренный в данной диссертации, однако последний формализм может описывать ещё более мощные конструкции и поэтому мало приемлем, например, для описания подклассов класса КС-языков с разрешимой проблемой эквивалентности. Исследование бесконечных множеств пар скобок является альтернативой магазинным автоматам и двухуровневым грамматикам. Для этого необходимо исследование бесконечных итераций языков, что и определяет актуальность данной работы. При этом одной из самых важных проблем - например, в упомянутом классе скобочных языков - является описание как можно более широких подклассов с разрешимой проблемой эквивалентности в них.