Введение
1 Предварительные сведения 16
2 Дескриптивная слолсность окрестности регулярного языка в метрике Хэмминга 24
2.1 Окрестность языка в метрике Хэмминга 24
2.2 Верхние оценки недетерминированной и детерминированной сложности 27
2.3 Нижняя оценка недетерминированной сложности . 31
2.4 Нижняя оценка детерминированной сложности 33
2.5 Сопоставление оценок детерминированной сложности и результатов экспериментов 47
3 Дескриптивная слолсность применения конечного трансдьюсера 54
3.1 Конечные трансдьюсеры 54
3.2 Недетерминированная сложность применения конечного трансдыосера 58
3.3 Детерминированная сложность применения конечного трансдьюсера 62
4 Дескриптивная слолсность динамической окрестности регулярного языка 64
4.1 Динамическая окрестность языка 64
4.2 Регулярность динамической окрестности регулярного языка 66
4.3 Верхняя оценка недетерминированной сложности . 69
Список литературы 72
