Gramatyka łączenia zakresów

Gramatyka łączenia zakresów (RCG) to formalizm gramatyczny opracowany przez Pierre'a Boulliera w 1998 roku jako próba scharakteryzowania szeregu zjawisk języka naturalnego, takich jak liczby chińskie i szyfrowanie kolejności słów w języku niemieckim , które wykraczają poza granice umiarkowanie kontekstowego języki .

Z teoretycznego punktu widzenia każdy język, który można analizować w czasie wielomianowym, należy do podzbioru RCG zwanego gramatyką konkatenacyjną o zakresie dodatnim i odwrotnie.

gramatyk ruchu dosłownego (LMG) Groeninka , RCG traktują proces gramatyczny bardziej jako dowód niż jako produkcję. Podczas gdy LMG tworzą ciąg końcowy z predykatu początkowego, RCG mają na celu redukcję predykatu początkowego (który jest predykatem ciągu końcowego) do pustego ciągu, co stanowi dowód przynależności ciągów końcowych do języka.

Opis

Definicja formalna

Gramatyka łączenia zakresu dodatniego (PRCG) to krotka , gdzie: ${\ displaystyle G = (N, ~ T, ~ V, ~ S, ~ P)}$

i $są$ rozłącznymi $skończonymi$ zbiorami (odpowiednio) nazw $nazw$ , symboli i zmiennych . Z każdą nazwą predykatu jest powiązana arność określona przez funkcję ${\ Displaystyle \ dim: N \rightarrow \ mathbb {N} \ setminus \ {0 \}}$ .
${\ Displaystyle S \ w N}$ to nazwa predykatu początkowego i sprawdź ${\ displaystyle \ dim (S) = 1}$ .
to skończony zbiór klauzul w postaci $\ rightarrow \ psi _ {1}$ $ldots \ psi _ {m}}$ są predykatami postaci $\ psi _ {i$ } ${\ Displaystyle A_ {i} (\ alfa _ {1}, \ ldots, \ alfa _ {\ dim (A_ {i}}})} z i ZA ja$ ∈ $A_ {i} \ w N$ } ${\ Displaystyle \ alfa _ {i} \ in (T \ puchar V) ^ {\ gwiazda}}$ .

Gramatykę łączenia zakresów ujemnych (NRCG) definiuje się podobnie jak PRCG, ale z dodatkiem, że niektóre predykaty występujące po prawej stronie zdania mogą mieć postać ${\ Displaystyle {\ overline {A_ {i} (\ alfa _ {1}, \ ldots, \ alfa _ {\ dim (A_ {i}}})}}}$ . Takie predykaty nazywane są predykatami negatywnymi .

Gramatyka łączenia zakresów jest gramatyczna dodatnia lub ujemna. Chociaż PRCG są technicznie NRCG, terminy te są używane do podkreślenia braku (PRCG) lub obecności (NRCG) negatywnych predykatów.

Zakres słowa ${\ Displaystyle w \ w T ^ {\ gwiazda}}$ to para $w}}$ , ${\ displaystyle 0 \ równoważnik l \ równoważnik r \ równoważnik n}$ , gdzie ${\ displaystyle n}$ jest długością ${\ displaystyle w}$ . Dwa zakresy ${\ Displaystyle \ langle l_ {1}, r_ {1} \ rangle _ {w}}$ i $}$ ${\ Displaystyle \ l_ l_ {2}, r_ {2} \ rangle _ {w$ połączyć $⋅$ mamy ${\ Displaystyle \ langle l_ {1}, r_ {1} \ rangle _ {w} \ cdot \ langle l_ {2}, r_ {2} \ rangle _ {w} = \ langle l_ {1 },r_{2}\rangle _{w}}$ .

Dla słowa ${\ displaystyle w = w_ {1} w_ {2} \ ldots w_ {n}}$ $\ displaystyle w_ {i} \ w T$ ja } oznaczenie zakresów z kropkami to: ${\ Displaystyle \ langle l, r \ rangle _ {w} = w_ {1} \ ldots w_ {l-1} \ kula w_ {l} \ ldots w_ {r-1} \ kula w_ {r} \ldots w_{n}}$ .

Rozpoznawanie ciągów

Podobnie jak LMG, klauzule RCG mają ogólny schemat, gdzie ${\ displaystyle A (x_ {1}, ..., x_ {n}) \ do \ alfa$ } RCG jest albo pustym ciągiem $znaków$ albo ciągiem predykatów. Argumenty składają się z ciągów symboli końcowych i/lub symboli zmiennych, których wzór pasuje do rzeczywistych wartości argumentów, jak $LMG$ Sąsiednie zmienne tworzą rodzinę dopasowań do partycji, więc argument $\ displaystyle xy}$ ${\ Displaystyle x = \ epsilon, \ y = ab; \ x = a, \ y = b; \ x = ab, \ y = \ epsilon}$ z dwiema zmiennymi dopasowuje dosłowny ciąg znaków $na$ trzy różne sposoby .

Terminy predykatów występują w dwóch postaciach, dodatniej (która w przypadku powodzenia generuje pusty ciąg znaków) i ujemną (która tworzy pusty ciąg znaków w przypadku niepowodzenia/jeśli termin dodatni nie generuje pustego ciągu ) . Terminy negatywne są oznaczane tak samo jak terminy pozytywne, z kreską górną, jak w ${\ displaystyle {\ overline {A (x_ {1}, ..., x_ {n })}}}$ .

Semantyka przepisywania dla RCG jest raczej prosta, identyczna z odpowiednią semantyką LMG. Biorąc pod $ZA$ ciąg predykatów , gdzie symbole są symbolami. $Displaystyle A (\ alfa _ {1}, ..., \ alfa _ {n})}$ są ciągami końcowymi, jeśli istnieje reguła $gramatyce,$ w której pasuje ciąg predykatów, ciąg predykatów jest zastępowany przez , zastępując ${\ displaystyle \ beta}$ $dopasowane$ w .

Na przykład, biorąc pod uwagę regułę , gdzie i $\ Displaystyle A (x, ayb) \ do B ($ , $)$ } $za$ ${\ displaystyle a}$ i symbolami końcowymi, a ciąg predykatów i $}$ ${\ Displaystyle A (a, abb$ $( za$ $b$ ponieważ ( $\ Displaystyle A (x, ayb)$ gdy , ${\ Displaystyle x = a, \ y = b}$ . Podobnie, gdyby istniała reguła, ${\ displaystyle A (x, ayb) \ do A (x, x) \ A (y, y)}$ , $\ Displaystyle A (a, abb)}$ można przepisać jako ${\ Displaystyle A (a, a) \ A (b, b)}$ .

Dowód / rozpoznanie ciągu $odbywa$ $tworzy$ poprzez pokazanie ciąg W poszczególnych etapach przepisywania, gdy możliwych jest wiele alternatywnych dopasowań zmiennych, uwzględniane jest każde przepisanie, które mogłoby doprowadzić do powodzenia całego dowodu. Zatem jeśli $istnieje$ najmniej jeden sposób na wygenerowanie pustego ciągu z początkowego ciągu dowód uważa się za udany, niezależnie od tego, ile innych sposobów na porażkę

Przykład

$_$ nieliniowy _ następująco:

Niech x, y i z będą symbolami zmiennymi:

${\ Displaystyle S (xyz) \ do A (x, y, z)}$

${\ Displaystyle A (topór, ay, az) \ do A (x, y, z)}$

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

${\ Displaystyle A (\ epsilon, \ epsilon, \ epsilon) \ do \ epsilon}$

Dowód na abbabbabb jest zatem

${\ Displaystyle S (abbabbabb) \ Strzałka w prawo A (abb, abb, abb) \ Strzałka w prawo A (bb, bb, bb) \ Strzałka w prawo A (b, b, b) \ Strzałka w prawo A (\ epsilon, \epsilon ,\epsilon )\Rightarrow \epsilon }$

Lub używając bardziej poprawnej notacji z kropkami dla zakresów:

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

^ Boullier, Pierre (styczeń 1998). Propozycja szkieletu składniowego przetwarzania języka naturalnego (PDF) (raport techniczny). Tom. 3342. INRIA Rocquencourt (Francja).
^ Pierre'a Boulliera (1999). „Gramatyki chińskich liczb, MIX, szyfrowania i łączenia zakresów” (PDF) . Proc. EACL . s. 53–60. Zarchiwizowane od oryginału (PDF) w dniu 2003-05-15.
^ Eberhard Bertsch i Mark-Jan Nederhof (październik 2001). „O złożoności niektórych rozszerzeń analizowania RCG” (PDF) . Materiały z siódmych międzynarodowych warsztatów na temat technologii analizy składniowej (Pekin) . s. 66–77.
^ Laury Kallmeyer (2010). Analizowanie poza gramatyką bezkontekstową . Springer Nauka i media biznesowe. P. 37. ISBN 978-3-642-14846-0 . cytując Bertscha, Nederhof (2001)

[boullier1998-1] Boullier, Pierre (styczeń 1998). Propozycja szkieletu składniowego przetwarzania języka naturalnego (PDF) (raport techniczny). Tom. 3342. INRIA Rocquencourt (Francja).

[boullier1999-2] Pierre'a Boulliera (1999). „Gramatyki chińskich liczb, MIX, szyfrowania i łączenia zakresów” (PDF) . Proc. EACL . s. 53–60. Zarchiwizowane od oryginału (PDF) w dniu 2003-05-15.

[3] Eberhard Bertsch i Mark-Jan Nederhof (październik 2001). „O złożoności niektórych rozszerzeń analizowania RCG” (PDF) . Materiały z siódmych międzynarodowych warsztatów na temat technologii analizy składniowej (Pekin) . s. 66–77.

[Kallmeyer2010-4] Laury Kallmeyer (2010). Analizowanie poza gramatyką bezkontekstową . Springer Nauka i media biznesowe. P. 37. ISBN 978-3-642-14846-0 . cytując Bertscha, Nederhof (2001)