Введение
1 Анализ логических конструкций формальных языков 9
1.1 Исследование алгоритмов формирования многомодульных программ..9
1.2 Языки и регулярные языки 11
1.2.1 Алфавиты и языки 12
1.2.2 Регулярные выражения 15
1.3 Автомате конечным числом состояний 18
1.3.1 Проектирование автомата с конечным числом состояний 18
1.3.2 Гипотеза отождествления 24
1.3.3 Префиксное замыкание 31
1.4 Просто звёздные языки 33
1.4.1 Ограничения размера языка 33
1.4.2 Однобуквенный автомат 35
1.4.3 Условия полиномиального роста 37
1.5. Исчисление предикатов и регулярные языки 39
1.5.1 Регулярные предикаты 39
1.5.2 Языки со многими переменными 41
1.5.3 Исчисление и замкнутость предикатов 43
Цель и задачи исследования 45
2 Применение алгебраической теории групп к разработке синтаксиса и семантики формальных языков 46
2.1 Группы, как языки 46
2.1.1 Структура автоматов для групп 46
2.1.2 Построение алгоритма для решения проблемы слов 51
2.2 Графы Кэли и изометрические неравенства 54
2.2.1 Превращение графа Кэли в метрическое пространство 58
2.2.2 Ограничение длин 63
2.3. Группы автоматов 66
2.3.1 Свойство Липшица для групп автоматов 66
2.3.2 Стандартные автоматы 69
2.3.3 Ограничение длин 72
2.4. Инвариантность при замене образующих 76
2.4.1 Изменение образующих 77
2.4.2 Улучшение автоматической структуры 80
2.4.3 Биавтоматичность 83
2.4.4 Префиксное замыкание групп автоматов 85
3 Применение комбинаторной топологии к исследованию лексической структуры формального языка 88
3.1 Квазигеодезические, псевдоизометрия, поочередная комбинация 88
3.2 Метрические пространства, метрики путей и геодезические 89
3.3 Кратчайшие строки 92
3.3.1 Множества конического типа 92
3.3.2 Нахождение уровня элемента группы 98
3.3.3 Применение теории Люстерника - Шнирельмана к множествам конического типа 100
3.4 Псевдоизометрии 107
3.4.1 Псевдоотображения 108
3.4.2 Равносильность группы и действующего пространства 112
3.4.3 Оценки числа стационарных точек 114
Выводы 121
4 Определение оценки сложности символьного текста в терминах тополо гических инвариантов 122
4.1 Приложение результатов теоретического исследования к решению задач лексического анализа 122
4.2 Взаимодействие основных фаз транслятора 123
4.3 Применение метода категорного анализа к процедуре идентификации символов входного потока 125
Выводы 127
Заключение 129
Список литературы 131
