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

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

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

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

Описание

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

А Грамматика конкатенации положительных диапазонов (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_ {я} ( альфа _ {1}, ldots, альфа _ { тусклый (A_ {i})})}$ с ${ displaystyle A_ {i} in N}$ и ${ Displaystyle альфа _ {я} в (Т чашка V) ^ { звезда}}$.

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

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

А классифицировать одним словом ${ Displaystyle ш в Т ^ { звезда}}$ пара ${ 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 ш = ш_ {1} ш_ {2} ldots ш_ {п}}$, с ${ 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 имеют общую схему ${ displaystyle A (x_ {1}, ..., x_ {n}) to alpha}$, где в RCG, ${ displaystyle alpha}$ либо пустая строка, либо строка предикатов. Аргументы ${ displaystyle x_ {i}}$ состоят из строк терминальных символов и / или переменных символов, шаблон которых соответствует фактическим значениям аргументов, как в LMG. Смежные переменные составляют семейство совпадений с разделами, так что аргумент ${ 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 А ( альфа _ {1}, ..., альфа _ {п})}$, где символы ${ displaystyle alpha _ {я}}$ являются терминальными строками, если есть правило ${ displaystyle A (x_ {1}, ..., x_ {n}) to beta}$ в грамматике, которой соответствует строка предиката, строка предиката заменяется на ${ displaystyle beta}$, заменяя согласованные переменные в каждом ${ displaystyle x_ {i}}$.

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

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

Пример

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

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

${ Displaystyle S (xyz) к А (х, y, z)}$

${ Displaystyle А (топор, ау, аз) к А (х, у, z)}$

${ Displaystyle A (bx, by, bz) к A (x, y, z)}$

${ Displaystyle А ( эпсилон, эпсилон, эпсилон) в эпсилон}$

Доказательство для 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, эпсилон, эпсилон) вправо эпсилон}$

Рекомендации