Теория автоматов

Теория автоматов исследует абстрактные вычислительные устройства, моделирующие обработку конечных строк над конечными алфавитами. На уровне школьной информатики ключевую роль играют конечные автоматы (детерминированные и недетерминированные), их эквивалентность регулярным выражениям, алгоритмы минимизации и методы подсчёта числа принимаемых слов фиксированной длины. Для ЕГЭ важно уметь: формально читать определения, строить и симулировать автоматы, переводить НКА→ДКА, минимизировать ДКА, анализировать язык, распознаваемый автоматом, а также считать количество слов определённой длины, принимаемых автоматом.

Алфавит, слово, язык: базис

Алфавит:          Σ – непустое конечное множество символов.

Слово:            w ∈ Σ*, конечная последовательность символов (возможно пустая).

Пустое слово:     ε, длина |ε| = 0.

Длина слова:      |w| – количество символов в w.

Конкатенация:     u·v – слово, полученное приписыванием v к u.

Язык:             L ⊆ Σ* – произвольное множество слов над Σ.

Замыкания и операции на языках:

Объединение:      L1 ∪ L2

Пересечение:      L1 ∩ L2

Разность:         L1 \ L2

Конкатенация:     L1·L2 = { u·v | u∈L1, v∈L2 }

Звезда Клини:     L* = ⋃_{k≥0} L^k,  где L^0={ε}, L^{k+1}=L·L^k

Реверс строки:    rev(w) – символы в обратном порядке;  rev(L)={ rev(w) | w∈L }.

Детерминированный конечный автомат (ДКА)

Определение. ДКА – пятёрка

M = <Σ, Q, δ, q0, F>,

где  Σ – алфавит,

     Q – конечное множество состояний,

     δ: Q × Σ → Q – функция переходов,

     q0 ∈ Q – начальное состояние,

     F ⊆ Q – множество принимающих (допускающих) состояний.

Расширенная функция переходов δ* (по словам):

δ*(q, ε)   = q

δ*(q, xa)  = δ( δ*(q, x), a ),  где x∈Σ*, a∈Σ

Приём слова:

w принимается автоматом M  ⇔  δ*(q0, w) ∈ F.

Язык автомата: L(M) = { w ∈ Σ* | δ*(q0, w) ∈ F }.

Технические замечания для корректных решений:

• ДКА часто делают полным: добавляют «стоковое» состояние ⊥ и определяют δ для всех пар (q, a). Это упрощает дополнение языка.

• Симуляция на слове – линейна по длине: O(|w|).

Недетерминированный КА (НКА) и ε-переходы

Определение. НКА – пятёрка

N = <Σ, Q, Δ, q0, F>,

Δ: Q × (Σ ∪ {ε}) → P(Q) – многозначная функция переходов,

остальное как у ДКА.

ε-замыкание: ε-closure(S) – множество состояний, достижимых из S по ε-переходам (включая сами состояния).

Семантика приёма: слово w принимается, если существует маршрут из q0 в некоторое состояние из F, согласованный с символами w, разрешая ε-переходы между чтениями символов.

Детерминизация (подстановочная конструкция)

Построим ДКА D = <Σ,  P(Q) , δ', S0, F'>, где:

S0     = ε-closure({q0})

δ'(S,a)= ε-closure( ⋃_{q∈S} Δ(q,a) )

F'     = { S ⊆ Q | S ∩ F ≠ ∅ }

После построения удаляют недостижимые множества-состояния. Языки эквивалентны: L(N)=L(D).

Регулярные выражения и регулярные языки

Регулярные выражения над Σ строятся из:

∅, ε, a∈Σ, используя операции:  (r1)|(r2) – объединение,

                                 (r1)(r2) – конкатенация,

                                 (r)*     – звезда Клини.

Класс языков, задаваемых регулярными выражениями, совпадает с классом языков, распознаваемых конечными автоматами.

• Из регулярного выражения к НКА – стандартная конструкция Томпсона (ε-переходы).
• Из ДКА к регулярному выражению – удаление состояний (state elimination).

Замкнутость и булева алгебра регулярных языков

Для регулярных языков справедливы замкнутости:

Объединение, пересечение, разность, дополнение,

конкатенация, звезда Клини, реверс, гомоморфизмы/обратные гомоморфизмы.

Практически важные построения для ДКА:

Дополнение:     если ДКА полный, то  L^c  принимает тот же автомат с множеством F' = Q \ F.

Пересечение:    декартово произведение состояний:  Q× = Q1×Q2,  F× = F1×F2,

                 δ×( (p,q), a ) = ( δ1(p,a), δ2(q,a) ).

Объединение:    аналогично,  F× = (F1×Q2) ∪ (Q1×F2).

Минимизация ДКА и теорема Майхилла–Нероуда

Два состояния p,q ∈ Q эквивалентны (неразличимы), если для любого слова x∈Σ*:

δ*(p, x) ∈ F  ⇔  δ*(q, x) ∈ F.

Факторизация по эквивалентности даёт минимальный (с точностью до изоморфизма) ДКА языка.

1. Табличный метод различимости (классический алгоритм)
   

   1. Удалить недостижимые состояния.

   2. Пометить все пары (p,q), где ровно одно из p,q находится в F.

   3. Итеративно помечать пары (p,q), если существует символ a∈Σ, такой что пара (δ(p,a), δ(q,a)) уже помечена.

   4. Непомеченные пары – классы эквивалентности, их склеиваем.

2. Быстрый метод Хопкрофта (эскиз)
   

   Итеративное уточнение разбиения P множества Q, стартуя с {F, Q\F}, разрезая классы под воздействием переходов. Сложность:

   O(|Σ| · |Q| · log|Q|)

   после удаления недостижимых состояний.

Подсчёт числа принимаемых слов длины n

Для ДКА M=<Σ,Q,δ,q0,F> удобно определить матрицу переходных кратностей A:

A[i,j] = количество символов a∈Σ, для которых δ(q_i,a) = q_j.

(Для классического ДКА без «слияний» по символам A[i,j] ∈ {0,1}, но с агрегацией по нескольким символам элемент может быть >1.)

Обозначим:

e0 – вектор-строка размера |Q| с 1 на позиции начального состояния q0 и 0 иначе.

f  – вектор-столбец размера |Q| с 1 на позициях из F и 0 иначе.

Тогда число слов длины n, принимаемых автоматом:

count(n) = e0 · (A^n) · f

Где умножение – обычное матричное; A^n можно вычислять быстрым возведением в степень за O(|Q|^3 log n) или динамикой:

dp[0] = e0

dp[k+1] = dp[k] · A

count(n) = dp[n] · f

Сложность динамики: O(n · |Q|^2), что часто достаточно для задач ЕГЭ.

Автоматы с выходом (Мили/Мура) – для программных фрагментов

Иногда в заданиях требуется по входному слову получить выход (цепочку символов/числовой счётчик).

Автомат Мили:  выход зависит от пары (состояние, входной символ).

Автомат Мура:  выход зависит только от состояния.

Оба типа эквивалентны по вычислительной мощности; преобразования между ними линейны по числу переходов/состояний. При ручной симуляции фиксируйте:

• момент генерации выхода (до/после перехода),
• начальное выходное значение,
• инвариант на накопленных данных.

Практические правила (для уверенных решений на ЕГЭ)

Правило 1. Табличная симуляция. Для входа w=a1…ak заполняйте таблицу строкой состояний: q0, q1=δ(q0,a1), …, qk. Ответ «принимает/не принимает» по факту qk ∈ F.

Правило 2. Удаляйте недостижимые состояния перед минимизацией. Иначе автомат не станет минимальным.

Правило 3. Для дополнения языка делайте ДКА полным. Добавьте сток ⊥ и все недостающие переходы в ⊥.

Правило 4. НКА→ДКА – затем (при необходимости) минимизация. Сначала детерминизация (подмножества), потом сжатие.

Правило 5. Подсчёты по длине – через DP/матрицы. Пишите явный рекуррент: переходы по всем символам, инициализация dp[0] единицей в q0.

Правило 6. Чётко фиксируйте алфавит. Множество символов влияет на матрицу A и количество слов.

Правило 7. Словари/шаблоны «окончание на …», «содержит …».

• «Оканчивается на s» – автомат, помнящий суффиксы s (фактор-префиксная функция).
• «Содержит s как подслово» – автомат КМП-типа по префикс-функции.

Типичные ловушки и как их избежать

• Неполные переходы в ДКА при дополнении языка → всегда добавляйте сток.
• Смешение НКА и ДКА при симуляции → в НКА симуляция ведётся по множеству текущих состояний (ε-closure!).
• Минимизация без удаления недостижимых → неверный результат.
• Подсчёт слов с неверным алфавитом → лишний множитель в A.
• Забытый ε при расширенной δ* → правильно определять δ*(q,ε)=q.

Мини-шпаргалка (копируемые формулы и конструкции)

ДКА:       M = <Σ, Q, δ, q0, F>

Расширение: δ*(q, ε)=q;  δ*(q, xa)=δ(δ*(q,x),a) 

НКА:       N = <Σ, Q, Δ, q0, F>,  Δ: Q×(Σ∪{ε})→P(Q)

Детерм.:   S0=ε-closure({q0});  δ'(S,a)=ε-closure(⋃_{q∈S}Δ(q,a)) 

Булева алгебра:

Дополнение (полный ДКА): F' = Q \ F

Пересечение: Q×=Q1×Q2, F×=F1×F2, δ×((p,q),a)=(δ1(p,a),δ2(q,a)) 

Минимизация (таблица различимости):

1) удалить недостижимые,

2) пометить (p,q), где p∈F, q∉F,

3) итеративно помечать по обратным образам переходов,

4) слить непомеченные пары. 

Подсчёт слов:

A[i,j] = #{ a∈Σ | δ(q_i,a)=q_j }

count(n) = e0 · A^n · f

Пять упражнений (академический формат)

Упражнение 1. Симуляция ДКА и анализ языка
Дан ДКА над Σ={0,1} с состояниями Q={q0,q1,q2}, q0 – начальное, F={q2}. Переходы:
δ(q0,0)=q0, δ(q0,1)=q1; δ(q1,0)=q2, δ(q1,1)=q0; δ(q2,0)=q2, δ(q2,1)=q1.
a) Просимулируйте работу на словах: ε, 1, 10, 101, 1010.
b) Сформулируйте язык L(M) неформально (словами) и кратко формально (например, через регулярное выражение).
c) Обоснуйте корректность описания (инвариант по префиксу входа).

Упражнение 2. НКА→ДКА (подстановочная конструкция)

Дан НКА над Σ={a,b} с состояниями Q={s,t,u}, начальное s, F={u}. Переходы:
Δ(s,a)={s,t}, Δ(s,b)={s}, Δ(t,b)={u}, Δ(t,a)={}; ε-переходов нет.
a) Постройте ДКА методом множеств, удалив недостижимые.
b) Укажите все переходы и множество принимающих состояний.
c) Дайте короткое регулярное выражение для полученного языка.

Упражнение 3. Минимизация ДКА (табличный метод)

Дан полный ДКА над Σ={0,1}, Q={A,B,C,D,E}, F={C,E}. Переходы:
δ(A,0)=B, δ(A,1)=C; δ(B,0)=A, δ(B,1)=D; δ(C,0)=E, δ(C,1)=A;
δ(D,0)=E, δ(D,1)=B; δ(E,0)=C, δ(E,1)=D.
a) Удалите недостижимые состояния (если есть).
b) Проведите табличную минимизацию и постройте минимальный автомат.
c) Напишите эквивалентное регулярное выражение (по желанию – через удаление состояний).

Упражнение 4. Подсчёт числа принимаемых слов длины n

ДКА над Σ={a,b}, Q={q0,q1}, q0 – начальное, F={q1}; переходы:
δ(q0,a)=q1, δ(q0,b)=q0; δ(q1,a)=q0, δ(q1,b)=q1.
a) Постройте матрицу A (в порядке q0,q1) и векторы e0, f.
b) Выведите формулу count(n)=e0·A^n·f и вычислите count(1), count(2), count(3).
c) Получите рекуррент для count(n) и решите его (подсказка: это числа слов с нечётным количеством a).

Упражнение 5. «Оканчивается на s» как автомат

Для Σ={0,1} постройте ДКА, распознающий язык слов, оканчивающихся на s=101.
a) Определите состояния как длины наибольшего суффикса входного префикса, совпадающего с префиксом s.
b) Выпишите δ в виде таблицы и множество F.
c) Докажите корректность через инвариант: в состоянии i автомата храним длину совпавшего префикса образца.

Заключение

Теория автоматов предоставляет компактный, строго определённый инструментарий для анализа и синтеза алгоритмов обработки строк: от симуляции ДКА/НКА до минимизации и подсчёта принимаемых слов. Для ЕГЭ владение этими понятиями – способ не только быстро решать типовые задачи (симуляция, перевод НКА→ДКА, минимизация), но и аргументированно обосновывать корректность решений. Следуя изложенным формальным правилам и отрабатывая упражнения, вы сформируете устойчивые навыки, необходимые для уверенных высоких баллов.