32
правки
Изменения
Правки
# Регулярное выражение <tex>(aba?)c(?1)\,</tex> породит язык <tex>L=\{abcab,abacab,abcaba,abacaba\}.\;</tex> Для сравнения, запишем эквивалентное регулярное выражение без использования механизма обратных ссылок: <tex>(aba?)c(aba?).</tex>
# <tex>(a^*)\backslash 1.\,</tex> Данное регулярное выражение будет допускать только слова, в которых количество букв <tex>a</tex> чётно.
# Выведем регулярное выражение для языка, состоящего из палиндромов фиксированной длины <tex>n=2\cdot m\,</tex> или <tex>\,n=2\cdot m+1</tex> над алфавитом <tex>\Sigma=\{0,1\}</tex>:#* для чётного <tex>n</tex>: <tex>\;\underbrace{(a_10\,|\,1)(a_20\,|\,1)(a_30\,|\,1)\dotsc(a_m0\,|\,1)}_{m}\,\backslash m\dotsc\backslash 3\backslash 2\backslash 1;</tex>#* для нечётного <tex>n</tex>: <tex>\;\underbrace{(a_10\,|\,1)(a_20\,|\,1)(a_30\,|\,1)\dotsc(a_m0\,|\,1)a_}_{m+}\,(0\,|\,1})\backslash m\dotsc\backslash 3\backslash 2\backslash 1,\;</tex> #: где <tex>a_i\in\Sigma</tex> для всех <tex>i.</tex>
# Запишем выражение для языка <tex>L=b^kab^kab^ka,\,k>0.\,</tex> Данный язык не является ни регулярным, ни контекстно-свободным (по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]]), то есть является [[Иерархия Хомского формальных грамматик|контекстно-зависимым]], но также легко представим с помощью обратных ссылок:
#: <tex>L=(bb^*a)\backslash 1\backslash 1</tex>.
Второе и третье правила не требуют использования обратных ссылок:
<tex>A\rightarrow a\leftrightarrow A\rightarrow (a);\\S\rightarrow\varepsilon\leftrightarrow S\rightarrow (\varepsilon).</tex>
Если какому-то нетерминалу <tex>A</tex> соответствуют несколько регулярных выражений <tex>r_1, r_2, \dotsc, r_n</tex>, заменить их на одно: <tex>A=(r_1\,|\,r_2\,|\,\dotsc\,|\,r_n)\,</tex> (очевидно, что оно также будет соответствовать этому нетерминалу).
Регулярное выражение для данной КС-грамматики соответствует нетерминалу <tex>S,\,</tex> однако в нём могут встречаться ссылки на внешние {{---}} отличные от <tex>S</tex> {{---}} группы. Будем обрабатывать такие ссылки, используя метод [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|левостороннего вывода]]. При обработке очередной ссылки:
# если эта ссылка встречается впервые, вместо неё подставим соответствующее регулярное выражение и запомним номер его группы в текущем регулярном выражении;
# иначе вместо этой ссылки подставим ссылку на соответствующую группув текущем регулярном выражении.
Таким образом, регулярное выражение для данной грамматики будет выглядеть так: <tex>(((c)(a))\,|\,((d)(?4))\,|\,((?3)(b))\,|\,((e)(?8))).</tex>
Рассмотрим другой пример:
<tex>S\rightarrow\varepsilon\\S\rightarrow (S)S\\S\rightarrow S(S)</tex>
# Приведём её к нормальной форме Хомского:
#: <tex>S\rightarrow\varepsilon\\S\rightarrow AS\\S\rightarrow SA\\A\rightarrow OB\\B\rightarrow SC\\O\rightarrow (\\C\rightarrow\; )</tex>
# Каждому нетерминалу поставим в соответствие свой номер:
#: <tex>S\leftrightarrow 1, A\leftrightarrow 2, B\leftrightarrow 3, O\leftrightarrow 4, C\leftrightarrow 5</tex>
# Каждое правило представим в виде регулярного выражения с обратными ссылками:
#: <tex>S\rightarrow ()\\S\rightarrow ((?2)(?1))\\S\rightarrow ((?1)(?2))\\A\rightarrow ((?4)(?3))\\B\rightarrow ((?1)(?5))\\O\rightarrow (\backslash (\,)\\C\rightarrow (\backslash )\,)</tex>
# Объединим регулярные выражения, соответствующие одинаковым нетерминалам:
#: <tex>S\rightarrow (()\,|\,((?2)(?1))\,|\,((?1)(?2)))\\A\rightarrow ((?4)(?3))\\B\rightarrow ((?1)(?5))\\O\rightarrow (\backslash (\,)\\C\rightarrow (\backslash )\,)</tex>
# Избавимся от внешних ссылок в регулярном выражении для <tex>S</tex>:
{| class="wikitable" style="display: inline-table; white-space: nowrap; text-align: center;"
|+Пошаговый вывод
! № || Текущее регулярное выражение
|-
| 1. || <tex>(()\,|\,((\underline{\textbf{?2}})(?1))\,|\,((?1)(\underline{?2})))</tex>
|-
| 2. || <tex>(()\,|\,(((\underline{\textbf{?4}})(\underline{?3}))(?1))\,|\,((?1)(\underline{?2})))</tex>
|-
| 3. || <tex>(()\,|\,(((\backslash (\,)(\underline{\textbf{?3}}))(?1))\,|\,((?1)(\underline{?2})))</tex>
|-
| 4. || <tex>(()\,|\,(((\backslash (\,)((?1)(\underline{\textbf{?5}})))(?1))\,|\,((?1)(\underline{?2})))</tex>
|-
| 5. || <tex>(()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(\underline{\textbf{?2}})))</tex>
|-
| 6. || <tex>(()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4)))</tex>
|}
{| class="wikitable" style="display: inline-table; white-space: nowrap; text-align: center;"
|+№ группы в <tex>S</tex>
! <tex>S</tex> || <tex>A</tex> || <tex>B</tex> || <tex>O</tex> || <tex>C</tex>
|-
| 1 || style="background: #1b5de2; color: white;" | || || ||
|-
| 1 || <b>4</b> || || style="background: #1b5de2; color: white;" | ||
|-
|-
| 1 || 4 || style="background: #1b5de2; color: white;" | || <b>5</b> ||
|-
| 1 || 4 || <b>6</b> || 5 || style="background: #1b5de2; color: white;" |
|-
| 1 || style="background: #1b5de2; color: white;" | 4 || 6 || 5 || <b>7</b>
|-
| 1 || 4 || 6 || 5 || 7
|}
Таким образом, регулярное выражение для данной грамматики будет выглядеть так: <tex>(()\,|\,(((\backslash (\,)((?1)(\backslash )\,)))(?1))\,|\,((?1)(?4))).</tex>
==Применение==
Регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые контекстно-зависимые (например, язык тандемных повторов).
