Pośrednie przykłady z formalnej teorii języka

Uczę się algebraicznej teorii parsowania. Moim pierwszym problemem jest zidentyfikowanie przykładów semieralnych, które są specyficzne dla formalnej teorii języka. Oto próba skonstruowania dwóch przykładów.

1 Biorąc pod uwagę gramatykę CNF, elementy semeryzacji są zestawami symboli terminalnych i nieterminalnych z operacjami:

i) Mnożenie , łączenie dwóch zestawów parami zgodnie z regułą CYK. Na przykład podana gramatyka CNF

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

następnie

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

ii) Dodawanie jest ustalane zjednoczeniem, np

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

Niestety, mnożenie nie jest skojarzone.

2 Elementy drugiego semestru to zbiory nie symboli, ale reguły gramatyczne [niekoniecznie w CNF] zmienione pozycją. Operacje są

i) Mnożenie , łączenie wszystkich pasujących par elementów zgodnie z regułą Earley complete. Na przykład podana gramatyka CNF

s: p q r 
r: s t | u

następnie

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

ii) Dodawanie jest ponownie ustalonym związkiem, np

$\{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\}$

Ten przykład jest również wadliwy.

Semery z elementami będącymi zestawami reguł gramatycznych, a mnożenie będące podstawieniem reguł wydaje się działać dobrze. Jest to jednak algebra relacji w przebraniu. Rzeczywiście, spójrzmy na każdą regułę gramatyczną jako klasę równoważności - zestaw par słów składających się z liter terminalnych i nieterminalnych związanych z zastosowaniem reguły, np.

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

Zatem rozpoznanie słowa w gramatyce jest łańcuchem relacji relacyjnych, np

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

(Ten monomial przypomina semierowanie wielomianu parsera z rozprawy doktorskiej Josha Goodmana; jednakże, powtórzmy, że konstruowanie nowych półprzewodników przez wzięcie wielomianów i macierzy nie jest w tym przypadku naszym zainteresowaniem).

Pozostaje więc pytanie: czy nazywanie języków formalnych na alfabet$\Sigma$ jedyny przykład?

Istnieje wiele semirings związanych z teorią języka. Przede wszystkim Boolean semiring. Następnie dowolna klasa języków zamknięta w ramach skończonej unii i produktu (konkatenacji) jest podzespołem semirowania wszystkich języków. Na przykład języki wymierne (= zwykłe) tworzą semiry. Zobacz także powiązane pojęcie algebry Kleene'a .

The $k \times k$macierze w ciągu semiringu tworzą semiring. W szczególności macierze powyżej semestru boolowskiego kodują niedeterministyczne automaty skończone i macierze w nieco większym semiringu$\{-\infty, 0, 1\}$kodować przejścia automatu Büchi. Macierze w ciągu semiery są używane do charakteryzowania serii wymiernych .

Te tropikalne semirings , w szczególności$(\mathbb{N} \cup \{+\infty\}, \min, +)$ i $(\mathbb{N} \cup \{-\infty\}, \max, +)$odgrywać znaczącą rolę w teorii automatów. Doprowadziły również do nowej gałęzi matematyki, tropikalnej geometrii .

Zabawa z Semirings: funkcjonalna perła na nadużyciu algebry liniowej

Efektywna analiza i dzielenie i parsowanie języków bezkontekstowych

Myślę, że możesz wymyślić więcej pół-pierścieni zgodnie z zasadami Earleya. Weź prognozę. Możesz utworzyć operator binarny$S\otimes_{p,k} T = S \cup \bigcup (Y: \bullet \gamma$, k) $ tak, że związek jest ponad wszystkimi odpowiednimi przepisami. Następnie algorytm najpierw oblicza pierwszy zestaw stanu Earleya jako nieskończony, ale ostatecznie powtarzający się (tak skończony) produkt w operatorze:

$S(0) = \bigotimes_{p,0}^{\infty} S_0(0)$. Nie wiem jednak, czy to tworzy pół-pierścień ze związkiem. Może to także tworzy relacje z innymi operacjami.