Кратко о формальной связи (теорема) и доказательство в двух направлениях.
Теорема. Класс регулярных выражений совпадает с классом языков, распознаваемых конечными автоматами (ДКА/НКА).
Доказательство (набросок).
1) Регулярное выражение ⇒ НКА (конструкция Томпсона).
- Базовые случаи: для символа $a$ строим НКА с двумя состояниями и переходом по $a$; для пустой строки $\epsilon$ — НКА с одним старт/приёмным состоянием; для пустого языка — НКА без приёмных состояний.
- Операции: объединение $r|s$, конкатенация $rs$ и звезда $r^{\ast }$ реализуются стандартными схемами с $\epsilon$-переходами (Томпсон). Каждое регулярное выражение порождает конечный НКА.
Следствие: любой язык, задаваемый регулярным выражением, распознаётся некоторым НКА.
2) Конечный автомат ⇒ регулярное выражение (методы: исключение состояний или лемма Ардена).
- Для ДКА/НКА можно поэтапно исключать состояния и записывать соответствующие регулярные выражения для путей между остающимися состояниями; в конце получаем регулярное выражение, равное языку автомата.
- Альтернативно, через систему уравнений для регулярных языков и применение леммы Ардена можно вывести регулярное выражение.
Следствие: любой язык, распознаваемый конечным автоматом, задаётся некоторым регулярным выражением.
Итого: классы совпадают.
Пример: построим НКА для регулярного выражения $(a|b{)}^{\ast }abb$ и выполним детерминизацию.
1) НКА (простая нерекурсивная конструкция, эквивалентная Томпсону).
Определим НКА $N=(Q,\Sigma ,\delta ,q_0,F)$, где
$$Q=\{q_0,q_1,q_2,q_3\},\Sigma =\{a,b\},F=\{q_3\}.$$ Переходы заданы нефункционально (множества):
$$\begin{array}{rl}\delta (q_0,a)& =\{q_0,q_1\},\\ \delta (q_0,b)& =\{q_0\},\\ \delta (q_1,b)& =\{q_2\},\\ \delta (q_2,b)& =\{q_3\},\end{array}$$ и все остальные $\delta (q,x)=\varnothing$. Начальное состояние $q_0$.
Комментарий: из $q_0$ по $a$ автомата может либо «начать» распознавание суффикса $abb$ (переход в $q_1$), либо оставаться в $q_0$ (символ принадлежит $(a|b{)}^{\ast }$). Это НКА без $\epsilon$-переходов.
2) Детерминизация (алгоритм подмножеств).
Начальное состояние ДКА — замыкание по $\epsilon$ множества $\{q_0\}$, здесь нет $\epsilon$-переходов, значит стартовый набор
$$S_0=\{q_0\}.$$ Выполним итеративно переходы множества:
$$\begin{array}{rl}{\delta }_D(\{q_0\},a)& =\delta (q_0,a)=\{q_0,q_1\}=S_1,\\ {\delta }_D(\{q_0\},b)& =\delta (q_0,b)=\{q_0\}=S_0.\end{array}$$ Далее для $S_1=\{q_0,q_1\}$:
$$\begin{array}{rl}{\delta }_D(S_1,a)& =\delta (q_0,a)\cup \delta (q_1,a)=\{q_0,q_1\}=S_1,\\ {\delta }_D(S_1,b)& =\delta (q_0,b)\cup \delta (q_1,b)=\{q_0,q_2\}=S_2.\end{array}$$ Для $S_2=\{q_0,q_2\}$:
$$\begin{array}{rl}{\delta }_D(S_2,a)& =\delta (q_0,a)\cup \delta (q_2,a)=\{q_0,q_1\}=S_1,\\ {\delta }_D(S_2,b)& =\delta (q_0,b)\cup \delta (q_2,b)=\{q_0,q_3\}=S_3.\end{array}$$ Для $S_3=\{q_0,q_3\}$:
$$\begin{array}{rl}{\delta }_D(S_3,a)& =\delta (q_0,a)\cup \delta (q_3,a)=\{q_0,q_1\}=S_1,\\ {\delta }_D(S_3,b)& =\delta (q_0,b)\cup \delta (q_3,b)=\{q_0\}=S_0.\end{array}$$ Новых состояний после $S_0,S_1,S_2,S_3$ не появляется. Приёмные состояния ДКА — те множества, которые содержат $q_3$, т.е. единственное из полученных это $S_3$.
Итоговый ДКА $D=(Q_D,\Sigma ,{\delta }_D,S_0,F_D)$:
$$Q_D=\{S_0,S_1,S_2,S_3\}=\{\{q_0\},\{q_0,q_1\},\{q_0,q_2\},\{q_0,q_3\}\},$$ старт $S_0=\{q_0\}$, приёмные $F_D=\{S_3\}$, переходы как выше:
$$\begin{array}{rlrl}{\delta }_D(S_0,a)& =S_1,& {\delta }_D(S_0,b)& =S_0,\\ {\delta }_D(S_1,a)& =S_1,& {\delta }_D(S_1,b)& =S_2,\\ {\delta }_D(S_2,a)& =S_1,& {\delta }_D(S_2,b)& =S_3,\\ {\delta }_D(S_3,a)& =S_1,& {\delta }_D(S_3,b)& =S_0.\end{array}$$
Краткое замечание: получившийся ДКА эквивалентен известному минимальному автомату для языка «строки над $\{a,b\}$, оканчивающиеся на подстроку $abb$» и имеет четыре состояния, соответствующие совпадению с суффиксами $\epsilon ,a,ab,abb$.
Если нужно, могу дать диаграммы автоматов или вывести регулярное выражение назад из полученного ДКА.