Регулярное выражение: $(ab|a{)}^{\ast }b$.
DFA (словесно и формально):
- Множество состояний: $Q=\{q_0,q_1,q_2,q_3,q_d\}$.
- Начальное состояние: $q_0$.
- Допускающие состояния: $F=\{q_2,q_3\}$.
- Интуитивный смысл состояний:
- $q_0$ — на границе токенов (старт или сразу после целого блока), нет незавершённого «a».
- $q_1$ — прочитана «a», она может быть либо отдельным блоком «a», либо началом блока «ab».
- $q_2$ — текущее слово может быть уже принятым (существует разбор, где финальный $b$ уже прочитан), но возможны дальнейшие корректные продолжения (то есть одновременно возможны варианты «ещё в цикле» и «уже закончено»).
- $q_3$ — слово точно заканчивается на финальный $b$ и дальнейшее чтение приведёт к провалу (финальный $b$ однозначно использован).
- $q_d$ — мёртвое состояние (невозможный префикс).
- Функция переходов (неполный список — остальные очевидны, переходы из $q_d$ в $q_d$):
- $\delta (q_0,a)=q_1$, $\delta (q_0,b)=q_3$.
- $\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_d$, $\delta (q_3,b)=q_d$.
- $\delta (q_d,a)=q_d$, $\delta (q_d,b)=q_d$.
Как проверять членство слова w в $L$:
1. Положить текущее состояние $=q_0$.
2. Последовательно для каждой буквы $c$ из $w$ переходить в состояние $\delta (\text{текущее},c)$.
3. После обработки всех символов: если текущее состояние принадлежит $F=\{q_2,q_3\}$, то $w\in L$, иначе $w\notin L$.
Короткие примеры:
- $"b"$: $q_0\stackrel{b}{}{q}_3$ — принимается.
- $"ab"$: $q_0\stackrel{a}{}{q}_1\stackrel{b}{}{q}_2$ — принимается.
- $"bb"$: $q_0\stackrel{b}{}{q}_3\stackrel{b}{}{q}_d$ — не принимается.
- $"abb"$: $q_0\stackrel{a}{}{q}_1\stackrel{b}{}{q}_2\stackrel{b}{}{q}_3$ — принимается.