Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Семынина, Татьяна Валерьевна
05.13.11
Кандидатская
2005
Воронеж
137 с. : ил.
Стоимость:
499 руб.
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 к
Название работы | Автор | Дата защиты |
---|---|---|
Способы и программные средства сравнения исполняемых файлов для их оперативной кластеризации | Антонов, Алексей Евгеньевич | 2013 |
Автоматический логический вывод в интуиционистских логических исчислениях обратным методом Маслова | Павлов, Владимир Александрович | 2017 |
Методы построения программных систем для автоматизации экспериментов в области спектрометрии нейтронов с использованием сетевых технологий | Саламатин, Кирилл Маркович | 2015 |