Verallgemeinerte kontextfreie Grammatik

Verallgemeinerte kontextfreie Grammatik (GCFG) ist ein Grammatikformalismus, der sich ausdehnt Kontextfreie Grammatiken Durch Hinzufügen von potenziell nicht kontextfreien Kompositionsfunktionen zum Umschreiben von Regeln.^[1] Kopfgrammatik (und seine schwachen Äquivalente) ist eine Instanz eines solchen GCFG, von dem bekannt ist, dass es besonders geschickt ist, eine Vielzahl von Nicht-CF-Eigenschaften der natürlichen Sprache zu bewältigen.

Beschreibung

Ein GCFG besteht aus zwei Komponenten: einer Reihe von Kompositionsfunktionen, die String -Tupel kombinieren, und eine Reihe von Umschreibegeln. Die Kompositionsfunktionen haben alle die Form $oder$ , wo ${\ displayStyle \ gamma}$ ist entweder ein einzelnes String -Tupel oder eine Verwendung einer (potenziell unterschiedlichen) Zusammensetzungsfunktion, die sich auf ein String -Tupel reduziert. Umschreiben von Regeln sehen aus wie ${\ displayStyle x \ bis f (y, z, ...)}$ , wo ${\ displayStyle y}$ , ${\ displayStyle z}$ , ... sind String-Tupel oder nicht terminale Symbole.

Die Umschreibungssemantik von GCFGs ist ziemlich einfach. Ein Auftreten eines nicht terminalen Symbols wird unter Verwendung von Neuschreibregeln wie in einer kontextfreien Grammatik neu geschrieben, wodurch schließlich nur Zusammensetzungen (Zusammensetzungsfunktionen auf String-Tupel oder andere Zusammensetzungen angewendet werden). Die Kompositionsfunktionen werden dann angewendet, wodurch die Tupel nacheinander auf ein einzelnes Tupel reduziert werden.

Beispiel

Eine einfache Übersetzung einer kontextfreien Grammatik in ein GCFG kann auf folgende Weise durchgeführt werden. Angesichts der Grammatik in (1), was die Palindrome -Sprache erzeugt ${\ displaystyle \ {ww^{r}: w \ in \ {a, b \}^{*} \}}, b \}^{*} \}}$ , wo ${\ displayStyle w^{r}}$ ist die Zeichenfolge umgekehrt von ${\ displayStyle W}$ Wir können die Kompositionsfunktion definieren konz wie in (2a) und die Umschreiben von Regeln wie in (in (2b).

{\ displayStyle s \ to \ epsilon ~ | ~ asa ~ | ~ bsb}

(1)

oder

(2a)

oder ~ conc (\ langle b \ rangle, s, \ Langle b \ rangle)}}

(2b)

Die CF -Produktion von Abbbba ist

S

Als ein

ABSBA

Abbsbba

Abbbba

und die entsprechende GCFG -Produktion ist

{\ displayStyle s \ to conc (\ langle a \ rangle, s, \ langle a \ rangle)}}

{\ displayStyle conc (\ Langle a \ rangle, conc (\ langle b \ rangle, s, \ Langle b \ rangle), \ Langle a \ rangle)}}

{\ displayStyle conc (\ Langle a \ rangle, conc (\ langle b \ rangle, conc (\ Langle B \ Rangle, s, \ Langle B \ Rangle), \ Langle B \ Rangle), \ Langle a \ Rangle)}}}

oder , \ 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), \ Langle a \ Rangle)}

{\ displayStyle conc (\ Langle a \ rangle, conc (\ langle b \ rangle, \ Langle bb \ rangle, \ Langle b \ rangle), \ langle a \ rangle)}}}}

{\ displayStyle conc (\ Langle a \ rangle, \ Langle Bbbb \ rangle, \ Langle a \ rangle)}}

{\ displayStyle \ Langle Abbbba \ rangle}

Lineare kontextfreie Umschreibungssysteme (LCFRS)

Weir (1988)^[1] Beschreibt zwei Eigenschaften von Zusammensetzungsfunktionen, Linearität und Regelmäßigkeit. Eine Funktion definiert als ${\ displayStyle f (x_ {1}, ..., x_ {n}) = ...}$ ist linear, wenn und nur dann, wenn jede Variable auf beiden Seiten der =, machen ${\ displayStyle f (x) = g (x, y)}$ linear aber nicht ${\ displayStyle f (x) = g (x, x)}$ . Eine Funktion definiert als ${\ displayStyle f (x_ {1}, ..., x_ {n}) = ...}$ ist regelmäßig, wenn die linke Seite und die rechte Seite genau die gleichen Variablen haben, die erstellen ${\ displayStyle f (x, y) = g (y, x)}$ regulär, aber nicht ${\ displayStyle f (x) = g (x, y)}$ oder ${\ displayStyle f (x, y) = g (x)}$ .

Eine Grammatik, in der alle Kompositionsfunktionen sowohl linear als auch regulär sind, wird als lineares kontextfreies Umschreibungssystem (LCFRs) bezeichnet. LCFRS ist a richtige Unterklasse von den GCFGs, d. H. Es hat streng weniger Rechenleistung als die GCFGs als Ganzes.

Andererseits sind LCFRS streng ausdrucksstarker als Linearindexierte Grammatiken und ihre schwach äquivalent Variante Baumgrammatik (Stichworte).^[2] Kopfgrammatik ist ein weiteres Beispiel für ein LCFRS, das streng weniger mächtig ist als die Klasse von LCFRS als Ganzes.

LCFRs entsprechen schwach zu (set-lokal) Mehrkomponent Tags (MCTAGs) und auch mit mehreren kontextfreien Grammatik (MCFGS [1]).^[3] und Minimalistische Grammatiken (MGS). Die von LCFRs (und ihre schwach entsprechenden) erzeugten Sprachen können analysiert werden Polynomzeit.^[4]

Siehe auch

Bereiche Verkettung Grammatik

Verweise

^ ^a ^b Weir, David Jeremy (September 1988). Charakterisieren leicht kontextsensitive Grammatikformalismen (PDF) (Ph.D.). Papier. Vol. AAI8908403. Universität von Pennsylvania Ann Arbor.
^ Laura Kallmeyer (2010). Analysen über kontextfreie Grammatiken übergehen. Springer Science & Business Media. p. 33. ISBN 978-3-642-14846-0.
^ Laura Kallmeyer (2010). Analysen über kontextfreie Grammatiken übergehen. Springer Science & Business Media. p. 35-36. ISBN 978-3-642-14846-0.
^ Johan F.A.K. Van Benthem; Alice Ter Meulen (2010). Handbuch der Logik und Sprache (2. Aufl.). Elsevier. p. 404. ISBN 978-0-444-53727-0.

[weir1988-1] Weir, David Jeremy (September 1988). Charakterisieren leicht kontextsensitive Grammatikformalismen (PDF) (Ph.D.). Papier. Vol. AAI8908403. Universität von Pennsylvania Ann Arbor.

[Kallmeyer2010-2] Laura Kallmeyer (2010). Analysen über kontextfreie Grammatiken übergehen. Springer Science & Business Media. p. 33. ISBN 978-3-642-14846-0.

[Kallmeyer2010b-3] Laura Kallmeyer (2010). Analysen über kontextfreie Grammatiken übergehen. Springer Science & Business Media. p. 35-36. ISBN 978-3-642-14846-0.

[BenthemMeulen2010-4] Johan F.A.K. Van Benthem; Alice Ter Meulen (2010). Handbuch der Logik und Sprache (2. Aufl.). Elsevier. p. 404. ISBN 978-0-444-53727-0.

[1]

[2]

[3]

[4]