# конспект · шаг 8 из 8
Конспект: конечные автоматы, недетерминизм и регулярные языки
Понятия
Язык - множество строк над алфавитом. Детерминированный конечный автомат, ДКА: конечный набор состояний, начальное, принимающие и таблица, где у каждой пары «состояние, символ» ровно одно следующее состояние. Регулярный язык - тот, который принимает какой-нибудь ДКА.
Недетерминированный автомат, НКА: в клетке таблицы множество состояний, возможно пустое; строка принята, если существует хотя бы один принимающий путь. ε-переход - смена состояния без чтения символа. Построение подмножеств - ДКА, состояния которого - множества состояний НКА.
Регулярное выражение - символы, ε и три операции: выбор, сцепление, повтор.
Различимые начала - два начала, к которым можно дописать один хвост так, что одна строка в языке, а другая нет. Лемма о накачке - в длинной строке регулярного языка есть кусок, который можно повторять.
Что унести
ДКА: одно состояние - всё, что известно о прошлом
делимость двоичного числа на 3: из остатка r по цифре b → (2r + b) mod 3
по 0 по 1
остаток 0 0 1 начало и принимающее
остаток 1 2 0
остаток 2 1 2
память не растёт с длиной строки; цена - один переход на символ
клетка, где «продолжения нет», - переход в ловушку, а не пустая клетка
НКА: «существует путь», а не случайный выбор
моделирование: множество возможных состояний;
новое = объединение переходов из всех текущих,
затем пополнить ε-переходами;
на символ - не больше числа переходов
пустое множество - строка отвергнута при любом продолжении
НКА → ДКА: состояния - множества; до 2ⁿ, строят только достижимые
«k-й символ с конца - единица»: НКА k + 1 ДКА 2ᵏ, и меньше нельзя
k = 3: 4 8
k = 8: 9 256
сила та же, запись короче - верно для конечных автоматов
и неверно для автоматов со стеком
РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ
a+ = a a* a? = a | ε [abc] = a | b | c a{3} = a a a
выражение длины m → НКА с O(m) состояниями (Томпсон) → и обратно;
длина - после раскрытия сокращений: a{1000} - это тысяча букв
ДКА, НКА, выражения - три записи одного класса языков
поиск множеством состояний O(n · m), плохих случаев нет RE2, Go, Rust
поиск с возвратами до экспоненты по длине строки Python, Java,
JS, Perl
зато умеет обратные ссылки \1 - а они
уже не регулярны
a*a*a*a*a*b на n буквах a: n 4 8 12 16
возвраты 252 2002 8568 26334
множества 24 48 72 96
(a+)+b на n буквах a: 2ⁿ⁻¹ разбиений; около секунды на 24 буквах,
вдвое больше на каждую следующую
опасные формы: повтор в повторе (a+)+
перекрывающийся выбор под повтором (a|aa)*
соседние повторы одного и того же .*.* \s*\s*
ЧЕГО АВТОМАТ НЕ МОЖЕТ
k состояний, k + 1 начало: ε, a, aa, …, aᵏ
→ два начала aⁱ, aʲ в одном состоянии
дописать bⁱ: aⁱbⁱ и aʲbⁱ получают один ответ, а в языке только первая
→ aⁿbⁿ не регулярен
бесконечно много попарно различимых начал → язык не регулярен
не регулярны: aⁿbⁿ правильные скобки палиндромы «a и b поровну»
регулярны: остаток по модулю глубина скобок не больше 5
aⁿbⁿ при n ≤ 100 a*b*
граница: хватает одного из конечного числа значений /
нужно помнить неограниченное число
дополнение: поменять принимающие и непринимающие состояния ДКА
пересечение: пары состояний, p · q состояний
есть алгоритм: пуст ли язык (обход графа);
равны ли два автомата (произведение и обход)
Минимизация ДКА: удалить недостижимые состояния, уточнять разбиение по классам целей переходов до устойчивости; классы соответствуют различимым языкам будущих продолжений.
Ловушки джокера
Оставил клетку таблицы пустой. У ДКА переход определён для каждой пары; невозможное продолжение ведёт в ловушку.
Решил, что НКА выбирает случайно. Вероятностей нет: принимающий путь либо существует, либо нет.
Моделировал НКА рекурсией по путям. Путей экспоненциально много, состояний - горстка; пути, пришедшие в одно состояние, нужно сливать.
Забыл пополнить множество ε-переходами. Принимающие пути теряются молча. Пополнять нужно и начальное множество.
Построил ДКА целиком и заранее. У НКА на сорок состояний их может быть триллион; строят достижимые, по мере надобности.
Проверил шаблон только на подходящих строках. Возвраты начинаются на строке, которая почти подходит.
Дал движку с возвратами шаблон или строку от пользователя. Повтор в повторе и тридцать символов - это минута процессора на один запрос.
Разбирал вложенные скобки регулярным выражением. Оно работает до глубины, на которую написано.
Счёл бесконечный язык нерегулярным. a* бесконечен и принимается одним состоянием.
Вывел регулярность из накачки. Лемма работает в одну сторону: регулярный язык накачивается, обратное неверно.
Проверь себя
Что именно помнит автомат о прочитанном? Почему недетерминизм не добавляет автоматам силы и сколько это
стоит? Чем поиск множеством состояний отличается от поиска с возвратами и почему второй до сих пор в
ходу? Как доказать, что язык не регулярен, не перебирая автоматы? Почему aⁿbⁿ при n ≤ 100 регулярен?
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий