32
правки
Изменения
Добавлены источники информации и ссылки на смежные темы
Порядок нумерации групп: сначала внешняя, потом вложенные (в порядке обхода в глубину).
==Применение==
С помощью обратных ссылок можно составить регулярные выражения для языка тандемных поворотов повторов и других языков, где требуется “запоминать” части входящих в язык слов.
Регулярные выражения в языках программирования зачастую поддерживают обратные ссылки. На практике их можно использовать, например, для парсинга html-выражений (поиск подстрок, содержащихся в определённых тегах).
==Примеры==
* Запишем [[Регулярные языки: два определения и их эквивалентность|регулярное выражение ]] для языка тандемных поворотов повторов над алфавитом <tex>\Sigma=\{0,1\}</tex>:
:<tex>L=((0|1)^∗)\backslash 1,</tex>
:где “«<tex>\backslash</tex>” » – символ обратной ссылки, который действует на первую группу. Обратная ссылка <tex>\backslash 1</tex> показывает, что после группы <tex>1</tex> {{---}} <tex>((0|1)^∗)</tex> {{---}} должен быть описан тот же текст, что содержится в ней.
:Данный язык не является регулярным, однако его можно представить с помощью регулярных выражений с использованием обратных ссылок.
# для нечётного <tex>n</tex>: <tex>\;(.)(.)(.)...(.).\backslash m...\backslash 3\backslash 2\backslash 1,\;</tex>
:где "«<tex>.</tex>" » – любой одиночный символ.
* Запишем регулярное выражение для языка <tex>L=b^kab^kab^ka</tex>. Данный язык не является ни регулярным, ни контекстно-свободным (по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]]), но также легко представим с помощью обратных ссылок:
:<tex>L=(b\{b\}^*a)\backslash 1\backslash 1</tex>
:<tex>L=(a(?1)?b),</tex>
:где «<tex>?1</tex> » – ссылка, осуществляющая рекурсивный вызов первой группы. Следущий за ссылкой знак вопроса обозначает использование группы <tex>0</tex> или <tex>1</tex> раз, то есть осуществление рекурсивного вызова или его окончание.
==Теорема о КС-языках==
{{Теорема
|id=theorem.
|statement=С помощью механизма обратных ссылок можно представить любой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]].
|proof=
По модулю определения определению контекстно-свободных языков. Любой свободного языка, любой КС-язык реализуется с помощью продукций нескольких видов; для каждого из них покажем, что его можно реализовать с использованием регулярных выражений с обратными ссылками.
Рассмотрим один из таких:
будет выглядеть так: <tex>((b\,|\,c)\,(?1)?).</tex>
То есть правила вида <tex>A\to BCD...\,</tex> реализуются при помощи ссылок на соответствующие группы, а для правил вида <tex>A\to A...\,</tex> используется обратная ссылка на ту же самую группу, для которой создаётся правило. При наличии нескольких правил в регулярном выражении пишется логическое “или”«или».
Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные, а также некоторые [[Иерархия Хомского формальных грамматик|контестно-зависимые]].
}}
* [[Регулярные языки: два определения и их эквивалентность]]
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
* [[Иерархия Хомского формальных грамматик]]
==Источники информации==
