Грамматика конкатенации диапазонов

Грамматика конкатенации диапазонов (RCG) - это грамматический формализм, разработанный Пьером Булье. в 1998 году как попытка охарактеризовать ряд явлений естественного языка, таких как китайские числа и скремблирование немецкого порядка слов , которые находятся за пределами умеренно контекстно-зависимых языков .

С теоретической точки зрения, любой язык, который можно анализировать за полиномиальное время, принадлежит к подмножеству RCG, называемому грамматиками конкатенации положительного диапазона, и наоборот.

Хотя RCG задуманы как вариант грамматик буквального движения Гренинка (LMG), они рассматривают грамматический процесс скорее как доказательство, чем как произведение. В то время как LMG создают терминальную строку из начального предиката, RCG стремятся свести начальный предикат (который предикаты терминальной строки) к пустой строке, которая представляет собой доказательство принадлежности терминальных строк языку.

Описание

Формальное определение

Грамматика конкатенации положительного диапазона (PRCG) представляет собой кортеж. $G=(N,~T,~V,~S,~P)$, где:

• $N$, $T$ и $V$ являются непересекающимися конечными множествами (соответственно) имен предикатов , терминальных символов и имен переменных . Каждое имя предиката имеет связанную с ним арность, задаваемую функцией $\dim :N\rightarrow \mathbb {N} \setminus \{0\}$.
• $S\in N$ — имя начального предиката и проверьте $\dim(S)=1$.
• $P$ представляет собой конечное множество предложений вида $\psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}$, где $\psi _{i}$ являются предикатами вида $A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})$ с $A_{i}\in N$ и $\alpha _{i}\in (T\cup V)^{\star }$.

Грамматика конкатенации отрицательного диапазона (NRCG) определяется как PRCG, но с тем дополнением, что некоторые предикаты, встречающиеся в правой части предложения, могут иметь форму ${\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}$. Такие предикаты называются отрицательными предикатами .

Грамматика конкатенации диапазонов может быть положительной или отрицательной. Хотя PRCG технически являются NRCG, ​​эти термины используются для обозначения отсутствия (PRCG) или присутствия (NRCG) отрицательных предикатов.

Диапазон одним словом $w\in T^{\star }$ это пара $\langle l,r\rangle _{w}$, с $0\leq l\leq r\leq n$, где $n$ длина $w$. Переменные привязываются к диапазонам, а не к произвольным строкам нетерминалов. Два диапазона $\langle l_{1},r_{1}\rangle _{w}$ и $\langle l_{2},r_{2}\rangle _{w}$ можно объединить, если и только если $r_{1}=l_{2}$, и тогда мы имеем: $\langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2}\rangle _{w}$. При создании экземпляра предложения, где аргумент состоит из нескольких элементов из $T\cup V$, их диапазоны должны объединиться.

На слово $w=w_{1}w_{2}\ldots w_{n}$, с $w_{i}\in T$, пунктирное обозначение диапазонов: $\langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}$.

Распознавание строк

Перезаписываемые строки предикатов представляют собой ограничения, которым должна удовлетворять проверяемая строка (если она положительна), а в случае отрицательных предикатов – не удовлетворяться. Порядок предикатов не имеет значения. Шаги перезаписи сводятся к замене одного ограничения нулем или более простыми ограничениями.

Как и LMG, положения RCG имеют общую схему. $A(x_{1},...,x_{n})\to \alpha$, где в RCG, $\alpha$ это либо пустая строка, либо строка предикатов. Аргументы $x_{i}$ состоят из строк терминальных символов и/или переменных символов, шаблон которых соответствует фактическим значениям аргументов, как в LMG. Соседние переменные составляют семейство совпадений с разделами, так что аргумент $xy$, с двумя переменными, соответствует буквальной строке $ab$ тремя разными способами: $x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon$. Это привело бы к трем различным вариантам реализации пункта, содержащего этот аргумент. $xy$.

Термины-предикаты бывают двух форм: положительные (которые создают пустую строку в случае успеха) и отрицательные (которые создают пустую строку в случае неудачи/если положительный термин не создает пустую строку). Отрицательные термины обозначаются так же, как и положительные, но с чертой, как в ${\overline {A(x_{1},...,x_{n})}}$.

Семантика перезаписи для RCG довольно проста и идентична соответствующей семантике LMG. Учитывая строку предиката $A(\alpha _{1},...,\alpha _{n})$, где символы $\alpha _{i}$ являются терминальными строками, если существует правило $A(x_{1},...,x_{n})\to \beta$ в грамматике, которой соответствует строка предиката, строка предиката заменяется на $\beta$, заменяя совпадающие переменные в каждом $x_{i}$.

Например, учитывая правило $A(x,ayb)\to B(axb,y)$, где $x$ и $y$ являются переменными символами и $a$ и $b$ являются терминальными символами, строка предиката $A(a,abb)$ можно переписать как $B(aab,b)$, потому что $A(a,abb)$ спички $A(x,ayb)$ когда $x=a,\ y=b$. Аналогично, если бы существовало правило $A(x,ayb)\to A(x,x)\ A(y,y)$, $A(a,abb)$ можно было бы переписать как $A(a,a)\ A(b,b)$.

Доказательство/распознавание строки $\alpha$ делается, показывая, что $S(\alpha )$ создает пустую строку. Для отдельных шагов перезаписи, когда возможны совпадения нескольких альтернативных переменных, рассматривается любая перезапись, которая может привести к успеху всего доказательства. Таким образом, если существует хотя бы один способ создать пустую строку из исходной строки $S(\alpha )$, доказательство считается успешным, независимо от того, сколько существует других способов потерпеть неудачу.

Пример

RCG способны распознавать нелинейный индексный язык. $\{www:w\in \{a,b\}^{*}\}$ следующее:

Пусть x, y и z будут переменными символами: $${\begin{aligned}S(xyz)&\to A(x,y,z)\\A(ax,ay,az)&\to A(x,y,z)\\A(bx,by,bz)&\to A(x,y,z)\\A(\epsilon ,\epsilon ,\epsilon )&\to \epsilon \end{aligned}}$$ Тогда доказательством для abbabbabb будет

$S(abbabbabb)\Rightarrow A(abb,abb,abb)\Rightarrow A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon$

Или, используя более правильное точечное обозначение диапазонов:

$S(\bullet {}abbabbabb\bullet {})\Rightarrow A(\bullet {}abb\bullet {}abbabb,abb\bullet {}abb\bullet {}abb,abbabb\bullet {}abb\bullet {})\Rightarrow A(a\bullet {}bb\bullet {}abbabb,abba\bullet {}bb\bullet {}abb,abbabba\bullet {}bb\bullet {})$ $\Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon$

Для строки $3n$ буквы, есть ${\binom {3n+2}{2}}={\frac {(3n+2)(3n+1)}{2}}$ различные реализации этого первого пункта, но только тот, который делает $x,y,z$ все $n$ буквы, каждая из которых позволяет вывести результат $\epsilon$.

Характеристики

Любую контекстно-свободную грамматику (CFG) можно преобразовать в грамматику конкатенации диапазонов:

• Для каждого нетерминала $A$ CFG, RCG имеет арность $1$ предикат $A(x)$.
• Для каждого правила CFG $A\to BC$, у RCG есть $A(xy)\to B(x)C(y)$.
• Для каждого правила CFG $A\to a$ (где $a$ терминал), RCG имеет $A(a)\to \epsilon$.

Пересечение и объединение двух языков конкатенации диапазонов тривиально представляют собой языки конкатенации диапазонов:

• Для $S$ пересечение $A$ и $B$, у вас есть $S(x)\to A(x)B(x)$.
• Для $S$ союз $A$ и $B$, у вас есть $S(x)\to A(x)$ и $S(x)\to B(x)$.

Возможно, языки конкатенации отрицательных диапазонов также закрываются при установленном дополнении.

Следствием вышесказанного является то, что неразрешимо, является ли язык конкатенации (положительных) диапазонов непустым, поскольку неразрешимо, непусто ли пересечение двух контекстно-свободных языков. Следовательно, грамматики конкатенации диапазонов не являются порождающими.