Кратко — как выполнить преобразование и в чём ограничения.
1) Регулярное выражение → конечный автомат (Thompson)
- Правила конструкции (построение NFA):
- Для символа $a$: NFA с состояниями $q_0,q_1$ и переходом $q_0\stackrel{a}{}{q}_1$.
- Для конкатенации $r_1{r}_2$: соединить финальные состояния NFA$r_1$ с начальным NFA$r_2$ через $\epsilon$-переходы.
- Для объединения $r_1|r_2$: новый старт $s$ с $\epsilon$-переходами к стартам NFA$r_1$ и NFA$r_2$, и новый финал с $\epsilon$-переходами от их финалов.
- Для звезды $r^{\ast }$: новый старт/финал, $\epsilon$-переходы в подавтомат и обратно, и $\epsilon$ напрямую в финал.
- После построения NFA можно получить DFA алгоритмом подмножеств (subset construction) и затем минимизировать.
2) Регулярное выражение → правая линейная КС-грамматика (через NFA)
- Сначала построить NFA $M=(Q,\Sigma ,\delta ,q_0,F)$.
- Построить грамматику $G=(V,\Sigma ,P,S)$, где $V=\{A_q\mid q\in Q\}$, $S=A_{q_0}$.
- Правила:
- Для каждого перехода $q\stackrel{a}{}p$ добавить производство $A_q\to a{A}_p$.
- Для каждого $\epsilon$-перехода $q\stackrel{\epsilon }{}p$ добавить $A_q\to A_p$.
- Для каждого принимающего состояния $q\in F$ добавить $A_q\to \epsilon$.
- Полученная грамматика правая линейная и генерирует тот же язык, что и исходное регулярное выражение.
Пример (коротко):
- Регулярное выражение $(a|b{)}^{\ast }ab$.
- Можно построить NFA по Thompson, а затем грамматику (примерное правило):
- $S\to aS\mid bS\mid aA$ - $A\to b$ (здесь $S$ соответствует стартовому состоянию, $A$ — состоянию перед финалом).
3) Ограничения регулярных выражений по сравнению с КС-языками
- Регулярные выражения описывают ровно регулярные языки; класс регулярных языков строго включён в класс контекстно-свободных языков.
- Регулярные языки не умеют описывать «сопоставление счётчиков» и вложенную структуру. Классический пример языка, который не регулярный, но контекстно‑свободный:
$$L=\{a^n{b}^n\mid n\ge 0\}.$$ Для него существует КС-грамматика $S\to aSb\mid \epsilon$, но никакого регулярного выражения не существует (это доказывается с помощью леммы о накачке для регулярных языков).
- Практические замечания: многие современные реализации «регулярных выражений» (PCRE и т.д.) поддерживают обратные ссылки и расширения, что делает их выразительнее — такие расширения выходят за рамки регулярных языков (и могут быть даже нерекурсивно тяжёлыми по сложности). Формально же регулярное выражение (в классическом смысле) — эквивалент регулярного автомата и правой линейной грамматики.
Коротко: алгоритмично: regex → (Thompson) NFA → (по необходимости) DFA → правая линейная КС‑грамматика по отображению состояний в нетерминалы. Ограничение: регулярные выражения не производят вложенных/согласованных по числу структур (например $a^n{b}^n$).