Коротко: минимальный ДКА имеет 4 состояния. Построение и доказательство минимальности ниже.
Автомат:
- Алфавит: $\{a,b\}$.
- Состояния: $Q=\{q_0,q_a,q_b,q_d\}$.
- Начальное: $q_0$.
- Принимающее: $\{q_0\}$ (пустая строка принадлежит $(ab|ba{)}^{\ast }$).
- Функция переходов $\delta$:
$$\begin{array}{rl}& \delta (q_0,a)=q_a,\delta (q_0,b)=q_b,\\ & \delta (q_a,b)=q_0,\delta (q_a,a)=q_d,\\ & \delta (q_b,a)=q_0,\delta (q_b,b)=q_d,\\ & \delta (q_d,a)=q_d,\delta (q_d,b)=q_d.\end{array}$$ Интуиция: $q_0$ — на границе пар (ожидаем первый символ пары); $q_a,q_b$ — прочитан первый символ пары $a$ или $b$ соответственно и ожидаем второй, отличающийся символ; $q_d$ — нарушение (любая дальнейшая строка недопустима).
Корректность: из $q_0$ чтение пары $ab$ или $ba$ возвращает в $q_0$, поэтому принимаются ровно конкатенации блоков $ab$ и $ba$, а любая некорректная пара переводит в $q_d$.
Доказательство минимальности (различимость состояний):
Покажем, что никакие два состояния не эквивалентны (существует разделяющая постфикс):
- $q_0$ и $q_a$: пустая строка $\epsilon$ различает (из $q_0$ $\epsilon$ принимается, из $q_a$ — нет).
- $q_0$ и $q_b$: аналогично $\epsilon$ различает.
- $q_0$ и $q_d$: $\epsilon$ различает ($q_0$ принимающее, $q_d$ — нет).
- $q_a$ и $q_b$: строка $b$ различает, т.к. $\delta (q_a,b)=q_0$ (принимает), а $\delta (q_b,b)=q_d$ (не принимает).
- $q_a$ и $q_d$: строка $b$ различает ($q_a\to q_0$ принимающее, $q_d\to q_d$ не принимающее).
- $q_b$ и $q_d$: строка $a$ различает ($q_b\to q_0$ принимающее, $q_d\to q_d$ не принимающее).
Таким образом все четыре состояния попарно различимы, значит нельзя сократить автомат до меньшего числа состояний. По теореме Майхила–Нерода это минимальный ДКА для языка $(ab|ba{)}^{\ast }$.