Semiring Beispiele aus der formalen Sprachtheorie

Ich lerne die algebraische Theorie des Parsens. Mein erstes Problem ist die Identifizierung von Semiring-Beispielen, die spezifisch für die formale Sprachtheorie sind. Hier ist ein Versuch, zwei Beispiele zu konstruieren.

1 Bei gegebener CNF-Grammatik sind die Elemente des Semirings Sätze von terminalen und nicht terminalen Symbolen mit den Operationen:

i) Multiplikation , paarweise Verbinden der beiden Sätze gemäß der CYK-Regel. Zum Beispiel gegebene CNF-Grammatik

s: p p | q r
t: p q
u: q q

dann

$\{p,q,r\}\otimes \{p,r\} = \{s,t\}$

ii) Addition ist Vereinigung gesetzt, z

$\{p,q\}\oplus \{q,r\} = \{p,q,r\}$

Leider ist die Multiplikation nicht assoziativ.

2 Die Elemente des zweiten Semirings sind Sätze von nicht Symbolen, sondern Grammatikregeln [nicht unbedingt in CNF], die mit der Position geändert wurden. Die Operationen sind

i) Multiplikation , bei der alle übereinstimmenden Elementpaare gemäß der vollständigen Earley-Regel verbunden werden. Zum Beispiel gegebene CNF-Grammatik

s: p q r 
r: s t | u

dann

$\{s: p \bullet q r,s: p q \bullet r\}\otimes \{r: u \bullet \} = \{s: p q r \bullet \}$

ii) Addition ist wieder die gesetzte Vereinigung, z

$\{s: p \bullet q r, r: \bullet s t\}\oplus \{r: u \bullet \} = \{s: p \bullet q r, r: \bullet s t, r: u \bullet\}$

Dieses Beispiel ist ebenfalls mangelhaft.

Semiring mit Elementen als Sätze von Grammatikregeln und Multiplikation als Regelsubstitution scheint gut zu funktionieren. Dies ist jedoch nur eine verschleierte Beziehungsalgebra. Betrachten wir in der Tat jede Grammatikregel als eine Äquivalenzklasse - eine Reihe von Wortpaaren, die aus End- und Nicht-Endbuchstaben bestehen, die durch die Anwendung der Regel in Beziehung stehen, z

$[t : s a] = \{ (t,sa),(ta,saa),(bt,bsa),(abt,absa),... \}$

Dann ist das Erkennen eines Wortes in einer Grammatik eine Kette relationaler Kompositionen, z

$[t:sa] \otimes [s:aa] \otimes \{(aaa,aaa)\} = \{(t,aaa)\}$

(Dieses Monom erinnert an das Semiring-Parser-Polynom aus der Doktorarbeit von Josh Goodman. Lassen Sie uns jedoch wiederholen, dass die Konstruktion neuer Semirings durch die Verwendung von Polynomen und Matrizen hier nicht von unserem Interesse ist.)

$\Sigma$

Es gibt viele semirings im Zusammenhang mit der Sprachtheorie. Zuallererst das Boolesche Semiring. Als nächstes ist jede Klasse von Sprachen, die unter endlicher Vereinigung und (Verkettungs-) Produkt geschlossen wird, ein Teil des Semirings aller Sprachen. Zum Beispiel bilden die rationalen (= regulären) Sprachen ein Semiring. Siehe auch den verwandten Begriff der Kleene-Algebra .

$k \times k$$\{-\infty, 0, 1\}$

$(\mathbb{N} \cup \{+\infty\}, \min, +)$$(\mathbb{N} \cup \{-\infty\}, \max, +)$

Spaß mit Semirings: Eine funktionale Perle zum Missbrauch der linearen Algebra

Effizientes Teilen und Erobern des Parsens kontextfreier Sprachen

$S\otimes_{p,k} T = S \cup \bigcup (Y: \bullet \gamma$

$S(0) = \bigotimes_{p,0}^{\infty} S_0(0)$