Регулярное выражение:
$$(a|b{)}^{\ast }\text{abba}(a|b{)}^{\ast }$$ (то есть все строки над $\{a,b\}$, которые содержат подстроку $\text{abba}$).
ДКА (конструкт KMP-подобный). Пусть состояния $\{q_0,q_1,q_2,q_3,q_4\}$, стартовое $q_0$, единственное принимающее $q_4$. Интерпретация состояния: в $q_i$ длина наибольшего префикса слова $\text{abba}$, являющегося суффиксом уже прочитанного входа, равна $i$. Переходы $\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_4,\delta (q_3,b)=q_0;\\ & \delta (q_4,a)=q_4,\delta (q_4,b)=q_4.\end{array}$$
Короткое пояснение построения: состояния соответствуют длинам совпавшего префикса $\text{abba}$ (0..4). При чтении символа обновляем длину совпавшего суффикса, делая "откат" по наиболее длинному возможному префиксу (как в KMP). Состояние $q_4$ — поглощающий, потому что после того как встретилась подстрока $\text{abba}$, любая дальнейшая часть строки всё ещё должна приниматься.
Доказательство корректности (инвариант + следствие):
Инвариант: после чтения любого префикса входного слова $w$ автомат находится в состоянии $q_i$ тогда и только тогда, когда $i$ — длина наибольшего префикса $\text{abba}$, являющегося суффиксом $w$.
Доказательство инварианта по индукции по длине префикса: для пустой строки верно (находятся в $q_0$). Пусть верно для строки $w$, докажем для $wa$ или $wb$: по определению переходов мы переводим текущее значение длины совпадающего суффикса в новое — именно в наибольшую возможную длину префикса $\text{abba}$, являющегося суффиксом расширенного слова (это прямое свойство построения переходов, аналогичное функции переходов в KMP). Таким образом инвариант сохраняется.
Следствие: принимающее состояние $q_4$ достигнуто после чтения некоторого префикса входа тогда и только тогда, когда этот префикс содержит подстроку $\text{abba}$. Поскольку $q_4$ поглощающий, автомат принимает ровно те слова, в каких встречается подстрока $\text{abba}$. Значит язык ДКА равен языку, порождаемому регулярным выражением выше.
Таким образом регулярное выражение и приведённый ДКА описывают один и тот же язык — все строки над $\{a,b\}$, содержащие подстроку $\text{abba}$.