Des exemples tirés de la théorie formelle du langage

J'apprends la théorie algébrique de l'analyse. Mon premier problème est d'identifier des exemples semi-spécifiques à la théorie formelle du langage. Voici une tentative de construire deux exemples.

1 Compte tenu de la grammaire CNF, les éléments de semiring sont des ensembles de symboles terminaux et non terminaux avec les opérations:

i) Multiplication , joignant les deux ensembles par paire selon la règle CYK. Par exemple, compte tenu de la grammaire CNF

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

puis

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

ii) L' addition est définie comme une union, par exemple

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

Malheureusement, la multiplication n'est pas associative.

2 Les éléments du second semiring sont des ensembles non pas de symboles mais de règles de grammaire [pas nécessairement en CNF] modifiées avec position. Les opérations sont

i) Multiplication , joignant toutes les paires d'éléments correspondants selon la règle complète d'Earley. Par exemple, compte tenu de la grammaire CNF

s: p q r 
r: s t | u

puis

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

ii) L' addition est à nouveau l'union définie, par exemple

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

Cet exemple est également déficient.

Semiring avec des éléments étant des ensembles de règles de grammaire et la multiplication étant une substitution de règles semble fonctionner correctement. Pourtant, ce n'est qu'une algèbre relationnelle déguisée. En effet, considérons chaque règle de grammaire comme une classe d'équivalence - un ensemble de paires de mots comprenant des lettres terminales et non terminales liées par l'application de la règle, par exemple

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

Ensuite, la reconnaissance d'un mot dans une grammaire est une chaîne de compositions relationnelles, par exemple

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

(Ce monôme rappelle le polynôme analyseur semi-conducteur de la thèse de Josh Goodman; cependant, répétons que la construction de nouveaux semi-anneaux en prenant des polynômes et des matrices n'est pas de notre intérêt ici).

Donc, la question demeure: est-ce que le semiring des langages formels sur l'alphabet le seul exemple? $\Sigma$

Il existe de nombreux semirings liés à la théorie du langage. Tout d'abord, le semi-booléen. Ensuite, toute classe de langues fermées sous un produit d'union et de concaténation finies est un sous-dépassement du semirage de toutes les langues. Par exemple, les langages rationnels (= réguliers) forment un semiring. Voir aussi la notion connexe d' algèbre de Kleene .

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

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

Fun with Semirings: Une perle fonctionnelle sur l'abus de l'algèbre linéaire

Analyse efficace de Divide and Conquer de langages sans contexte

Je pense que vous pouvez trouver plus de demi-anneaux avec les règles d'Earley. Prenez la prédiction. Vous pouvez former l'opérateur binaire , k) $ de telle sorte que l'union est sur toutes les règles pertinentes existantes. Ensuite, l'algorithme calcule d'abord le premier jeu d'états d'Earley comme un produit infini mais finalement répétitif (donc fini) dans l'opérateur:$S\otimes_{p,k} T = S \cup \bigcup (Y: \bullet \gamma$

$S(0) = \bigotimes_{p,0}^{\infty} S_0(0)$ . Je ne sais pas si cela forme un demi-anneau avec l'union cependant. Peut-être que cela crée également des relations avec d'autres opérations.