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

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

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

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

Описание [ править ]

Формальное определение [ править ]

Положительный диапазон Concatenation Грамматик (PRCG) является кортежем , где:${\ Displaystyle G = (N, ~ T, ~ V, ~ S, ~ P)}$

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

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

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

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

Для слова , с , то пунктирная обозначения для диапазонов: .${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$${\displaystyle w_{i}\in T}$${\displaystyle \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 имеют общую схему , где в RCG - это либо пустая строка, либо строка предикатов. Аргументы состоят из строк терминальных символов и / или переменных символов, шаблон которых соответствует фактическим значениям аргумента, как в LMG. Прилегающие переменные представляют собой семейство матчей с перегородками, так что аргумент , с двумя переменными, совпадает с символьной строки тремя различными способами: .${\displaystyle A(x_{1},...,x_{n})\to \alpha }$${\displaystyle \alpha }$${\displaystyle x_{i}}$${\displaystyle xy}$${\displaystyle ab}$${\displaystyle x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon }$

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

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

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

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

Пример [ править ]

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

Пусть x, y и z - символы переменных:

${\displaystyle S(xyz)\to A(x,y,z)}$

${\displaystyle A(ax,ay,az)\to A(x,y,z)}$

${\displaystyle A(bx,by,bz)\to A(x,y,z)}$

${\displaystyle A(\epsilon ,\epsilon ,\epsilon )\to \epsilon }$

Доказательство для abbabbabb тогда

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

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

${\displaystyle 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 {})}$ ${\displaystyle \Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

Ссылки [ править ]