32
правки
Изменения
м
Представим Представим каждое из них в виде регулярного выражения с обратными ссылками.
Используя Используя ссылки на регулярные выражения, соответствующие нетерминалам <tex>B</tex> и <tex>C</tex>, можно представить первое правило:
<tex>A\rightarrow a\leftrightarrow A=a;</tex>
<tex>S\rightarrow\varepsilon\leftrightarrow S=\varepsilon.</tex>
Правки
:где «<tex>?1</tex>» – ссылка, осуществляющая рекурсивный вызов первой группы. Следущий за ссылкой знак вопроса обозначает использование группы <tex>0</tex> или <tex>1</tex> раз, то есть осуществление рекурсивного вызова или его окончание.
:<tex>?1</tex> ссылается на первую группу {{---}}
<tex>(a(?1)?b)</tex>, что равносильно рекурсивной зависимости:
::::<tex>(a(?1)?b)=</tex>
:::<tex>=(a(a(?1)?b)?b)=</tex>
::<tex>=(a(a(a(?1)?b)?b)?b)=</tex>
|statement=С помощью механизма обратных ссылок можно представить любой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободный язык]].
|proof=
Любую контекстно-свободную грамматику можно привести к [[Нормальная форма Хомского|нормальной форме Хомского]], следовательно, достаточно доказать, что грамматику, заданную в нормальной форме, можно преобразовать в регулярное выражение с обратными ссылками.
Рассмотрим Рассмотрим правила, которые могут содержаться в такой грамматике:
<tex>A\rightarrow BC</tex>
<tex>
AA\rightarrow a</tex>
<tex>
SS\rightarrow\varepsilon</tex>
<tex>A\rightarrow BC\leftrightarrow A=((?B)\,(?C)).\,</tex>
Второе и третье правила не требуют использования обратных ссылок:
Таким образом, регулярные выражения с обратными ссылками имеют бо́льшую мощность по сравнению с обычными. С их помощью реализуются как регулярные языки, так и контекстно-свободные грамматики, а также некоторые [[Иерархия Хомского формальных грамматик|контекстно-зависимые]].
