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

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

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

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

Описание

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

Грамматика конкатенации положительного диапазона (PRCG) представляет собой кортеж , где: Г = ( Н ,   Т ,   В ,   С ,   П ) {\displaystyle G=(N,~T,~V,~S,~P)}

  • Н {\displaystyle N} , и являются непересекающимися конечными множествами (соответственно) предикатных имен , терминальных символов и имен переменных . Каждое предикатное имя имеет связанную арность, заданную функцией . Т {\displaystyle Т} В {\displaystyle V} тусклый : Н → Н ∖ { 0 } {\displaystyle \dim :N\rightarrow \mathbb {N} \setminus \{0\}}
  • С ∈ Н {\displaystyle S\in N} это имя начального предиката и проверка . тусклый ⁡ ( С ) = 1 {\displaystyle \dim(S)=1}
  • П {\displaystyle P} представляет собой конечный набор предложений вида , где являются предикатами вида с и . ψ 0 → ψ 1 … ψ м {\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{м}} ψ я {\displaystyle \psi _{i}} А я ( α 1 , … , α тусклый ⁡ ( А я ) ) {\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, но с добавлением того, что некоторые предикаты, встречающиеся в правой части предложения, могут иметь форму . Такие предикаты называются отрицательными предикатами . А я ( α 1 , … , α тусклый ⁡ ( А я ) ) ¯ {\displaystyle {\overline {A_{i}(\alpha _{1},\ldots,\alpha _{\dim(A_{i})})}}}

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

Диапазон в слове — это пара , с , где — длина . Переменные привязываются к диапазонам, а не к произвольным строкам нетерминалов. Два диапазона и могут быть объединены , если и только если , и тогда мы имеем: . При создании экземпляра предложения, где аргумент состоит из нескольких элементов из , их диапазоны должны быть объединены. ж ∈ Т ⋆ {\displaystyle w\in T^{\star }} ⟨ л , г ⟩ ж {\displaystyle \langle l,r\rangle _{w}} 0 ≤ л ≤ г ≤ н {\displaystyle 0\leq l\leq r\leq n} н {\displaystyle n} ж {\displaystyle w} ⟨ л 1 , г 1 ⟩ ж {\displaystyle \langle l_{1},r_{1}\rangle _{w}} ⟨ л 2 , г 2 ⟩ ж {\displaystyle \langle l_{2},r_{2}\rangle _{w}} г 1 = л 2 {\displaystyle r_{1}=l_{2}} ⟨ л 1 , г 1 ⟩ ж ⋅ ⟨ л 2 , г 2 ⟩ ж = ⟨ л 1 , г 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 T\чашка V}

Для слова с точками запись диапазонов выглядит так: . ж = ж 1 ж 2 … ж н {\displaystyle w=w_{1}w_{2}\ldots w_{n}} ж я ∈ Т {\displaystyle w_{i}\in T} ⟨ л , г ⟩ ж = ж 1 … ж л − 1 ∙ ж л … ж г − 1 ∙ ж г … ж н {\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. Смежные переменные составляют семейство соответствий с разделами, так что аргумент с двумя переменными сопоставляется с буквальной строкой тремя различными способами: . Это приведет к трем различным инстанциациям предложения, содержащего этот аргумент . А ( х 1 , . . . , х н ) → α {\displaystyle A(x_{1},...,x_{n})\to \альфа } α {\displaystyle \альфа} х я {\displaystyle x_{i}} х у {\displaystyle xy} а б {\displaystyle ab} х = ϵ ,   у = а б ;   х = а ,   у = б ;   х = а б ,   у = ϵ {\ displaystyle x = \ epsilon, \ y = ab; \ x = a, \ y = b; \ x = ab, \ y = \ epsilon } х у {\displaystyle xy}

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

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

Например, если задано правило , где и являются переменными символами, а и являются терминальными символами, предикатную строку можно переписать как , поскольку соответствует, когда . Аналогично, если бы было правило , можно было бы переписать как . А ( х , а у б ) → Б ( а х б , у ) {\displaystyle A(x,ayb)\to B(axb,y)} х {\displaystyle x} у {\displaystyle у} а {\displaystyle а} б {\displaystyle б} А ( а , а б б ) {\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 А(а,а)\ А(б,б)}

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

Пример

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

Пусть x, y и z будут переменными символами: Тогда доказательство для abbabbabb выглядит так: С ( х у з ) → А ( х , у , з ) А ( а х , а у , а з ) → А ( х , у , з ) А ( б х , б у , б з ) → А ( х , у , з ) А ( ϵ , ϵ , ϵ ) → ϵ {\displaystyle {\begin{align}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{align}}}

С ( а б б а б б а б б ) ⇒ А ( а б б , а б б , а б б ) ⇒ А ( б б , б б , б б ) ⇒ А ( б , б , б ) ⇒ А ( ϵ , ϵ , ϵ ) ⇒ ϵ {\displaystyle S(abbabbabb)\Стрелка вправо A(abb,abb,abb)\Стрелка вправо A(bb,bb,bb)\Стрелка вправо A(b,b,b)\Стрелка вправо A(\epsilon ,\epsilon ,\epsilon )\Стрелка вправо \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 }

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

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

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

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

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

  • Для пересечения и имеем . S {\displaystyle S} A {\displaystyle A} B {\displaystyle B} S ( x ) → A ( x ) B ( x ) {\displaystyle S(x)\to A(x)B(x)}
  • Для объединения и имеем и . S {\displaystyle S} A {\displaystyle A} B {\displaystyle B} S ( x ) → A ( x ) {\displaystyle S(x)\to A(x)} S ( x ) → B ( x ) {\displaystyle S(x)\to B(x)}

Языки конкатенации с возможным отрицательным диапазоном также закрыты относительно дополнения множеств.

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

Ссылки

  1. ^ Булье, Пьер (январь 1998 г.). Предложение по синтаксической основе обработки естественного языка (PDF) (технический отчет). Том 3342. INRIA Rocquencourt (Франция).
  2. ^ Пьер Булье (1999). «Китайские числа, MIX, скремблирование и грамматика конкатенации диапазонов» (PDF) . Proc. EACL . стр.  53–60 . Архивировано из оригинала (PDF) 2003-05-15.
  3. ^ Эберхард Берч и Марк-Ян Недерхоф (октябрь 2001 г.). «О сложности некоторых расширений анализа RCG» (PDF) . Труды Седьмого международного семинара по технологиям анализа (Пекин) . стр.  66–77 .
  4. ^ Лора Каллмейер (2010). Анализ за пределами контекстно-свободных грамматик . Springer Science & Business Media. стр. 37. ISBN 978-3-642-14846-0.цитируя Берча, Недерхофа (2001) [3]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Range_concatenation_grammar&oldid=1199074837"