Uogólniona gramatyka bezkontekstowa

Uogólniona gramatyka bezkontekstowa (GCFG) to formalizm gramatyczny, który rozszerza gramatyki bezkontekstowe , dodając potencjalnie bezkontekstowe funkcje składu w celu przepisania reguł. Gramatyka głowy (i jej słabe odpowiedniki) jest przykładem takiego GCFG, o którym wiadomo, że jest szczególnie biegły w obsłudze szerokiej gamy właściwości języka naturalnego innych niż CF.

Opis

GCFG składa się z dwóch komponentów: zestawu funkcji składu, które łączą krotki łańcuchowe, oraz zestawu reguł przepisywania. Wszystkie funkcje kompozycji mają postać $\ langle x_ {1} ,..., x_ {m} \ rangle, \ langle y_ {1},..., y_ {n} \ rangle,...) = \ gamma} ,$ gdzie ${\ Displaystyle \ gamma}$ jest albo a pojedyncza krotka łańcuchowa lub użycie (potencjalnie innej) funkcji składu, która redukuje się do krotki łańcuchowej. Reguły przepisywania wyglądają tak, gdzie ${\ Displaystyle X \ do f (Y, Z, ...)}$ , gdzie ${\ Displaystyle Y}$ , ${\ Displaystyle Z}$ . .. to krotki ciągów znaków lub symbole nieterminalne.

Semantyka przepisywania GCFG jest dość prosta. Wystąpienie symbolu nieterminalnego jest przepisywane przy użyciu reguł przepisywania, jak w gramatyce bezkontekstowej, ostatecznie dając tylko kompozycje (funkcje kompozycji zastosowane do krotek łańcuchów lub innych kompozycji). Następnie stosowane są funkcje kompozycji, sukcesywnie redukując krotki do pojedynczej krotki.

Przykład

Proste tłumaczenie gramatyki bezkontekstowej na GCFG można wykonać w następujący sposób. Biorąc pod uwagę gramatykę w ( 1 ), która generuje język palindromu ${\ Displaystyle \ {ww ^ {R}: w \ w \ {a, b \} ^ { *}\}}$ , gdzie $łańcuchem$ odwrotnym od , możemy zdefiniować funkcję kompozycji conc jak w ( $}}$ ) i reguły przepisywania jak w ( 2b ) w R {\ displaystyle w ^ ).

{\ Displaystyle S \ do \ epsilon ~ | ~ aSa ~ | ~ bSb}

()

{\ Displaystyle conc (\ langle x \ rangle, \ langle y \ rangle, \ langle z \ rangle) = \ langle xyz \rangle }

()

{\ Displaystyle S \ do conc (\ langle \ epsilon \ rangle, \ langle \ epsilon \ rangle, \ langle \ epsilon \ rangle) ~ | ~ conc (\ langle a\rangle ,S,\langle a\rangle )~|~conc(\langle b\rangle ,S,\langle b\rangle )}

()

Produkcja CF abbbba jest

S

aSa

abSba

abbSbba

abbba

a odpowiednia produkcja GCFG wynosi

{\ Displaystyle S \ do conc (\ langle a \ rangle, S, \ langle a \ rangle)}

rangle )}

{\ Displaystyle conc (\ langle a \ rangle, conc (\ langle b \ rangle, S, \ langle b \ rangle), \ langle a

{\ Displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}

{\ Displaystyle conc (\ langle a \ rangle, conc (\ langle b \ rangle, conc (\ langle b \ rangle, conc (\ langle \ epsilon \ rangle, \ langle \ epsilon \ rangle, \ langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}

{\ Displaystyle conc (\ langle a \ rangle, conc (\ langle b \ rangle, conc (\ langle b \ rangle, \langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}

_

{\ Displaystyle conc (\ langle a \ rangle, \ langle bbbb \ rangle, \ langle a \ rangle)}

{\ Displaystyle \ langle abbba \ rangle}

Liniowe bezkontekstowe systemy przepisywania (LCFRS)

Weir (1988) opisuje dwie właściwości funkcji składu, liniowość i regularność. Funkcja ${\ Displaystyle f (x_ {1}, ..., x_ {n}) =...}$ jest liniowy wtedy i tylko wtedy, gdy każda zmienna pojawia się co najwyżej raz po obu stronach = , co daje ${\ Displaystyle f (x) = g (x, y)}$ liniowy, ale nie ${\ Displaystyle f (x) = g (x, x)}$ . Funkcja ${\ Displaystyle f (x_ {1}, ..., x_ {n}) =...}$ jest regularny, jeśli lewa i prawa strona mają dokładnie te same zmienne, co daje ${\ Displaystyle f (x, y) = g (y, x)}$ regularne, ale nie ${\ Displaystyle f (x) = g (x, y) }$ lub ${\ Displaystyle f (x, y) = g (x)}$ .

Gramatyka, w której wszystkie funkcje składu są zarówno liniowe, jak i regularne, nazywana jest liniowym bezkontekstowym systemem przepisywania (LCFRS). LCFRS jest odpowiednią podklasą GCFG, tzn. ma zdecydowanie mniejszą moc obliczeniową niż GCFG jako całość.

Z drugiej strony, LCFRS są zdecydowanie bardziej wyraziste niż gramatyki indeksowane liniowo i ich słabo równoważne gramatyki sąsiadujące z drzewem wariantów (TAG). Gramatyka głowy to kolejny przykład LCFRS, który jest zdecydowanie mniej wydajny niż klasa LCFRS jako całość.

LCFRS są słabo równoważne (ustawionym lokalnie) wieloskładnikowym TAG (MCTAG), a także wielu gramatyce bezkontekstowej (MCFG [1] ). i minimalistyczne gramatyki (MG). Języki generowane przez LCFRS (i ich słabe odpowiedniki) mogą być analizowane w czasie wielomianowym .

Zobacz też

Gramatyka łączenia zakresów

^ ^a ^b Weir, David Jeremy (wrzesień 1988). Charakteryzowanie łagodnie kontekstowych formalizmów gramatycznych (PDF) (doktorat). Papier. Tom. AAI8908403. Uniwersytet Pensylwanii Ann Arbor.
^ Laura Kallmeyer (2010). Analiza poza gramatyką bezkontekstową . Springer Science & Business Media. P. 33. ISBN 978-3-642-14846-0 .
^ Laura Kallmeyer (2010). Analiza poza gramatyką bezkontekstową . Springer Science & Business Media. P. 35-36. ISBN 978-3-642-14846-0 .
Bibliografia _ Alice ter Meulen (2010). Podręcznik logiki i języka (wyd. 2). Elsevier. P. 404. ISBN 978-0-444-53727-0 .

[weir1988-1] Weir, David Jeremy (wrzesień 1988). Charakteryzowanie łagodnie kontekstowych formalizmów gramatycznych (PDF) (doktorat). Papier. Tom. AAI8908403. Uniwersytet Pensylwanii Ann Arbor.

[Kallmeyer2010-2] Laura Kallmeyer (2010). Analiza poza gramatyką bezkontekstową . Springer Science & Business Media. P. 33. ISBN 978-3-642-14846-0 .

[Kallmeyer2010b-3] Laura Kallmeyer (2010). Analiza poza gramatyką bezkontekstową . Springer Science & Business Media. P. 35-36. ISBN 978-3-642-14846-0 .

[BenthemMeulen2010-4] Bibliografia _ Alice ter Meulen (2010). Podręcznik logiki i języka (wyd. 2). Elsevier. P. 404. ISBN 978-0-444-53727-0 .