Язык:
- Регулярное выражение: $(a|b{)}^{\ast }abb$.
- Язык $L=\{w\in \{a,b{\}}^{\ast }\mid w\text{оканчивается на}abb\}$ — все строки над $\{a,b\}$, которые имеют суффикс «abb».
NFA (недетерминированный КА):
- Состояния $Q=\{q_0,q_1,q_2,q_3\}$, начальное $q_0$, принимающее $q_3$.
- Переходы (без $\epsilon$-переходов):
$$\begin{array}{rlrl}\delta (q_0,a)& =\{q_0,q_1\},& \delta (q_0,b)& =\{q_0\},\\ \delta (q_1,a)& =\varnothing ,& \delta (q_1,b)& =\{q_2\},\\ \delta (q_2,a)& =\varnothing ,& \delta (q_2,b)& =\{q_3\},\\ \delta (q_3,a)& =\varnothing ,& \delta (q_3,b)& =\varnothing .\end{array}$$ - Интерпретация: $q_0$ реализует $(a|b{)}^{\ast }$ (петля по $a,b$) и недетерминированный переход по $a$ в цепочку $a-b-b$ через $q_1,q_2,q_3$.
DFA (методом подмножеств) — построение иreachable множества:
- Начальное состояние DFA: $\{q_0\}$.
- Вычисляем переходы:
$$\begin{array}{rlrl}{\delta }_D(\{q_0\},a)& =\{q_0,q_1\},& {\delta }_D(\{q_0\},b)& =\{q_0\};\\ {\delta }_D(\{q_0,q_1\},a)& =\{q_0,q_1\},& {\delta }_D(\{q_0,q_1\},b)& =\{q_0,q_2\};\\ {\delta }_D(\{q_0,q_2\},a)& =\{q_0,q_1\},& {\delta }_D(\{q_0,q_2\},b)& =\{q_0,q_3\};\\ {\delta }_D(\{q_0,q_3\},a)& =\{q_0,q_1\},& {\delta }_D(\{q_0,q_3\},b)& =\{q_0\}.\end{array}$$ - Достижимые состояния DFA: $\{q_0\},\{q_0,q_1\},\{q_0,q_2\},\{q_0,q_3\}$. Принимающее — любое множество, содержащее $q_3$, т.е. $\{q_0,q_3\}$.
Удобно переименовать состояния:
$$S_0=\{q_0\},S_1=\{q_0,q_1\},S_2=\{q_0,q_2\},S_3=\{q_0,q_3\}(\text{принимающее}).$$ Тогда таблица переходов DFA:
$$\begin{array}{ccc}& a& b\\ S_0& S_1& S_0\\ S_1& S_1& S_2\\ S_2& S_1& S_3\\ S_3& S_1& S_0\end{array}$$
Минимизация DFA:
- Разбиение по принимающим/непринимающим: $\{S_3\}$ и $\{S_0,S_1,S_2\}$.
- Проверка различимости внутри непринимающих:
- У $S_2$ переход по $b$ ведёт в $S_3$ (принимающее), у $S_0,S_1$ — нет, значит $S_2$ отделяется.
- Далее $S_0$ и $S_1$ различны (переход по $b$: $S_0\to S_0$, $S_1\to S_2$ — в разные классы).
- В результате получаем четыре класcа $\{S_0\},\{S_1\},\{S_2\},\{S_3\}$ — автомат минимален и имеет 4 состояния (то есть DFA уже минимален).
Итог (минимальный DFA): четыре состояния с переходами, приведёнными в таблице выше, начальное $S_0$, принимающее $S_3$. Этот автомат распознаёт язык всех слов, оканчивающихся на «abb».