1) Формальное определение минимального ДКА.
Определим автомат $M=(Q,\Sigma ,\delta ,q_0,F)$, где
- $\Sigma =\{a,b\}$,
- $Q=\{q_0,q_1,q_2,q_3\}$,
- $q_0$ — начальное состояние,
- $F=\{q_3\}$,
- переходы $\delta$ заданы как
$$\begin{array}{rl}& \delta (q_0,a)=q_1,\delta (q_0,b)=q_0,\\ & \delta (q_1,a)=q_1,\delta (q_1,b)=q_2,\\ & \delta (q_2,a)=q_1,\delta (q_2,b)=q_3,\\ & \delta (q_3,a)=q_3,\delta (q_3,b)=q_3.\end{array}$$
Интерпретация состояний: $q_0$ — никакой суффикс текущей строки не соответствует префиксу «abb»; $q_1$ — последний символ «a» (совпадает с префиксом «a»); $q_2$ — последние символы «ab»; $q_3$ — уже найдено «abb» (принимающее состояние, зацикленное).
Число состояний: $|Q|=4$. Этот автомат минимален (Myhill–Nerode): состояния различимы по возможным продолжениям, дающим принятие/отклонение (нулевой, «a», «ab», «abb» дают разные эквивалентные классы).
2) Описание языка словами и регулярное описание.
Язык — множество всех слов над алфавитом $\{a,b\}$, которые содержат подпоследовательность (подстроку) «abb» подряд. Эквивалентное регулярное выражение: $(a|b{)}^{\ast }abb(a|b{)}^{\ast }$.
3) Оптимизация распознавания в стриминговой системе.
- Для одной фиксированной подстроки «abb» оптимальный алгоритм — тот же DFA: односканирующий алгоритм с постоянным состоянием. Память: $O(1)$ (нужно хранить только текущее состояние, можно закодировать в 2 битах). Время: $O(n)$ по длине входа.
- Реализация в стриме: держать текущее состояние и на каждый пришедший символ делать переход по таблице $\delta$; при достижении $q_3$ можно:
- если нужно только узнать наличие — немедленно завершить поток для данного ключа (early exit);
- если нужно подсчитать вхождения — инкрементировать счетчик при переходе в $q_3$ и продолжать (автомат корректно учитывает возможные перекрытия).
- Практические оптимизации:
- представлять состояние как небольшое целое (2 бита) и использовать таблицу переходов размером $|Q|\times |\Sigma |=4\times 2$ для branchless-обновлений (минимизирует ветвления);
- если нужно искать много шаблонов — строить автомат Aho–Corasick (многошаблонный DFA) или для одного длинного шаблона — префикс-функция KMP (оба остаются потоковыми и работают за $O(n)$);
- в высоконагруженных системах: пакетная обработка байтов с SIMD или заранее маппинг входных символов (например любой не-{a,b} → отдельный переход) для уменьшения накладных расходов на преобразование.
- Сложности: для шаблона фиксированной короткой длины DFA — наилучший выбор; для множества шаблонов или длинных шаблонов — использовать Aho–Corasick/KMP по необходимости.
Если нужны конкретные куски кода (псевдокод или таблица переходов для реализации в вашем стриме), уточните язык/платформу.