Разработка категорных средств анализа формальных языков на основе теории конических типов

• Автор: Семынина, Татьяна Валерьевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Воронеж
• Количество страниц: 137 с. : ил.

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

1Л Исследование алгоритмов формирования многомодульных программ

1.2 Языки и регулярные языки

1.2.1 Алфавиты и языки

1.2.2 Регулярные выражения

1.3 Автомат с конечным числом состояний

1.3.1 Проектирование автомата с конечным числом состояний

1.3.2 Гипотеза отождествления

1.3.3 Префиксное замыкание

1.4 Просто звёздные языки

1.4.1 Ограничения размера языка

1.4.2 Однобуквенный автомат
1.4.3 Условия полиномиального роста
1.5. Исчисление предикатов и регулярные языки
1.5.1 Регулярные предикаты
1.5.2 Языки со многими переменными
1.5.3 Исчисление и замкнутость предикатов
Цель и задачи исследования
2 Применение алгебраической теории групп к разработке синтаксиса и семантики формальных языков
2.1 Группы, как языки
2.1.1 Структура автоматов для групп
2.1.2 Построение алгоритма для решения проблемы слов
2.2 Графы Кэли и изометрические неравенства

2.2.1 Граф Кэли для различных групп
2.2.2 Превращение графа Кэли в метрическое пространство
2.2.3 Ограничение длин
2.3. Группы автоматов
2.3.1 Свойство Липшица для групп автоматов
2.3.2 Стандартные автоматы
2.3.3 Ограничение длин
2.4. Инвариантность при замене образующих
2.4.1 Изменение образующих
2.4.2 Улучшение автоматической структуры
2.4.3 Биавтоматичность
2.4.4 Префиксное замыкание групп автоматов
Выводы
3 Применение комбинаторной топологии к исследованию лексической структуры формального языка
3.1 Квазигеодезические, псевдоизометрия, поочередная комбинация
3.2 Метрические пространства, метрики путей и геодезические
3.3 Кратчайшие строки
3.3.1 Множества конического типа
3.3.2 Нахождение уровня элемента группы
3.3.3 Применение теории Люстерника - Шнирельмана к множествам конического типа
3.4 Псевдоизометрии
3.4.1 Псевдоотображения
3.4.2 Равносильность группы и действующего пространства
3.4.3 Оценки числа стационарных точек
Выводы
4 Определение оценки сложности символьного текста в терминах топологических инвариантов
4.1 Приложение результатов теоретического исследования к решению задач лексического анализа
4.2 Взаимодействие основных фаз транслятора
4.3 Применение метода категорного анализа к процедуре идентификации
символов входного потока
Выводы
Заключение
Список литературы
Рисунок 2.1. Автомат для свободной группы.
Этот частный автомат допускает в точности редуцированные строки в свободной группе с двумя образующими х и у.
Этот пример может быть обобщен на группу в и множество А полу-групповых образующих. Положим Ь равное множеству строк над А, которые являются кратчайшими представлениями для элементов в. Отображение л:Ь—обычно не является биективным, но оно является съюрективным и конечно - однозначным (то есть прообразом одного элемента может быть только конечное множество), потому что для каждого § все элементы из Ь в прообразе л'1^) имеют одинаковую длину и поэтому их конечное число.
Пусть в является свободной абелевой группой над тремя групповыми образующими х,у и г. И пусть А={х,у,г, Х,У,2}. Если Ь является языком, определенным регулярным выражением (х*уХ*)(у*мУ*)(г*м2*) то отображение Ьвб является биективным.
Пусть в является группой матриц размерами 3x3 с целыми коэффициентами, а именно, единицами - под диагональю и нулями над диагональю.
Матрицы х ~
образуют в как группу; имеем [х,у]=г и г коммутирует с х и у.
а 0 0^ Г1 0 0^ (1 0 0'
1 1 0 >У = 0 1 0 = 0 1
0 0 ,0 1 к -1 0 к