Введение
2 Модификации конечных автоматов 17
2.1 Регулярные языки и выражения 18
2.2 Простейшие конечные автоматы 20
2.2.1 Недетерминированный конечный автомат 20
2.2.2 Детерминированный конечный автомат 22
2.2.3 Детерминированный конечный мультиавтомат 23
2.3 Конечные автоматы с модифицированными переходами 25
2.3.1 Алгоритм Ахо-Корасик 25
2.3.2 Детерминированный конечный автомат с задержкой 27
2.3.3 Двойной автомат 31
2.3.4 Расширенный детерминированный конечный автомат 34
2.4 Выводы 40
3 Модификация двух выражений 42
3.1 Алгоритм объединения выражений 43
3.2 Оценка числа состояний 45
3.2.1 Вспомогательные утверждения 48
3.2.2 Доказательство теоремы 1 53
3.3 Применение алгоритма 58
4 Модификация произвольного числа выражений 60
4.1 Оценка числа состояний 61
4.1.1 Вспомогательные утверждения 63
4.1.2 Доказательство теоремы 2 70
4.1.3 Доказательство теоремы 3 77
4.1.4 Доказательство теоремы 4 85
4.2 Применение алгоритма 85
5 Оценка роста языка при модификации выражений 87
5.1 Способ оценки 88
5.1.1 Вспомогательные утверждения 90
5.1.2 Доказательство теоремы 5 104
5.2 Применение алгоритма 106
Заключение 110
Список литературы 111
