Trouver la factorisation maximale des langues régulières

Que language soit régulier.$\mathcal{L} \subseteq \Sigma^*$

Une factorisation de est une paire maximale d'ensembles de mots avec$\mathcal{L}$$(X,Y)$

• $X \cdot Y \subseteq \mathcal{L}$
• $X \neq \emptyset \neq Y$ ,

où | .$X \cdot Y = \{xy$$x \in X, y \in Y\}$

$(X,Y)$ est maximal si pour chaque paire avec soit ou Y \ pas \ subseteq Y ' .$(X',Y') \neq (X,Y)$$X'\cdot Y' \subseteq \mathcal{L}$$X \not \subseteq X'$$Y \not \subseteq Y'$

Existe-t-il une procédure simple pour savoir quelles paires sont maximales?

Exemple:

Soit $\mathcal{L} = \Sigma^∗ab \Sigma^∗$ . L'ensemble $F = \{u, v, w\}$ est calculé:

• $u =(\Sigma^∗, \Sigma^∗ab\Sigma^∗)$

• $v = (\Sigma^∗a\Sigma^∗, \Sigma^∗b\Sigma^∗)$

• $w = (\Sigma^∗ab\Sigma^∗, \Sigma^∗)$

où $\Sigma = \{a,b\}$ .

Un autre exemple:

$\Sigma = \{a, b\}$ et $\mathcal{L} = \Sigma^*a\Sigma$ Ensemble de factorisation Sigma $F = \{q, r, s, t\}$ avec

• $q = (\Sigma^*, \mathcal{L})$

• $r = (\Sigma^*a, \Sigma + \mathcal{L})$

• $s = (\Sigma^*aa, \epsilon + \Sigma + \mathcal{L})$

• $t = (\mathcal{L}, \epsilon + \mathcal{L})$

Comme suggéré dans les commentaires à la question, je vais essayer de donner une réponse (malheureusement partielle) à la question, au moins dans la mesure où j'ai compris le problème moi-même (cela implique que vous pourriez bien trouver des erreurs, et si vous trouvez un moyen d'expliquer plus brièvement ou clairement l'un des points ci-dessous, n'hésitez pas à modifier la réponse en conséquence):

Tout d'abord, il convient de noter que nous n'avons pas réellement à calculer l'automate universel d'une langue si nous voulons calculer les factorisations d'une langue.

D'après l'article mentionné dans mon commentaire ¹, il existe une correspondance 1-1 entre les facteurs gauche et droit d'une langue régulière, c'est-à-dire, étant donné un facteur gauche de la langue, le facteur droit correspondant est uniquement déterminé et vice versa. Plus précisément, nous avons les éléments suivants:

Let est une factorisation de L . Alors Y = ⋂ x ∈ X x - 1 L , X = ⋂ y ∈ Y L y - 1 , c'est-à-dire que tout facteur gauche est une intersection de quotients droits, et tout facteur droit est une intersection de quotients gauches. A l' inverse, une intersection de quotients gauche de L est un facteur droit de L , et toute intersection de droite quotients de L est un facteur gauche de L .$(X,Y)$$L$

Notez que pour une langue régulière, il n'y a qu'un ensemble fini de quotients gauche et droit, et donc ou le problème se réduit à calculer les quotients gauche et droit d'une langue, puis à calculer leur fermeture stable , c'est-à-dire un minimum surensemble des quotients qui est fermé sous l'intersection. Ceux - ci sont alors précisément les bons facteurs et les facteurs à gauche, et il est généralement facile de voir quelles paires sont des sous - ensembles de L .$\cap$$L$

Exemple

Afin d'illustrer les points ci-dessus, considérons le premier exemple de la question (dont je pense également qu'il est incorrect dans le document):

Soit . Maintenant, les quotients de gauche L sont les ensembles x - 1 L pour x ∈ Σ * , qui est, ces mots u dans Σ * qui peut être préfixé par x , soit x u ∈ L . Quand y - 1 L = x - 1 L pour x , y distincts ? C'est le cas si et seulement si $L = \Sigma^\ast ab \Sigma^\ast$$L$$x^{-1}L$$x\in \Sigma^\ast$$u$$\Sigma^\ast$$x$$xu \in L$$y^{-1}L=x^{-1}L$$x,y$$x$et peut être augmenté de mots en L avec exactement les mêmes suffixes. Cela signifie, pour le dire en termes plus familiers, qu'ils sont équivalents à Nérode, et les suffixes nécessaires pour ajouter des mots dans une classe Nérode sont précisément les quotients de gauche respectifs.$y$$L$

Pour , nous voyons que nos classes d'équivalence Nerode sont$L$

• , l'ensemble de mots ne contenant pas a b comme facteur et se terminant par a , $N_1$$ab$$a$
• , l'ensemble de mots se terminant par b et ne contenant pas a b comme facteur, et $N_2$$b$$ab$
• , l'ensemble de mots contenant a b comme facteur, c'est-à-dire N 3 = $N_3$$ab$$N_3 = L$

Ils peuvent être augmentés avec les ensembles suivants (c'est-à-dire que ce sont les quotients de gauche des mots dans les classes respectives):

• pour x dans N 1 se compose de tous les mots dans L (tout mot peut être augmenté d'un mot contenant a b comme facteur et devient ainsi un mot dans L ) et b Σ ∗ , c'est-à-dire S 1 = L ∪ b Σ $S_1 = x^{-1}L$$x$$N_1$$L$$ab$$L$$b\Sigma^\ast$$S_1 = L \cup b\Sigma^\ast$
• pour x dans N 2 est la langue elle-même, c'est-à-dire S 2 = L et$S_2 = x^{-1}L$$x$$N_2$$S_2 = L$
• pour x dans N 3 est évidemment Σ ∗ . Autrement dit, nous avons trouvé trois bons facteurs de L . Comme S 2 ⊂ S 1 ⊂ S 3 , leur ∩ fermeture -stable est trivialement S 1 , S 2 , S 3 , et ce sont alors précisément les facteurs appropriés.$S_3 = x^{-1}L$$x$$N_3$$\Sigma^\ast$$L$$S_2\subset S_1\subset S_3$$\cap$${S_1,S_2,S_3}$

Par conséquent, notre ensemble de factorisation est de la forme ( P 1 , S 1 ) , ( P 2 , S 2 ) , ( P 3 , S 3 ) .$\mathcal{F}_L$$(P_1,S_1),(P_2,S_2),(P_3,S_3)$

Maintenant, pour les facteurs de gauche , nous utilisons les équations du début de cette réponse:$P_i$

.

Pour , on obtient L ∪ Σ * a , pour P 2 nous obtenons Σ * et P 3 , on obtient L . Vous pouvez le voir par inspection (l'excuse la plus populaire pour être trop paresseux pour énoncer une preuve formelle) ou en calculant explicitement les bons quotients (ce qui est assez analogue, mais pas complètement, au calcul des quotients de gauche). Nos factorisations sont donc données par F L = u , v , w où$P_1$$L \cup \Sigma^\ast a$$P_2$$\Sigma^\ast$$P_3$$L$$\mathcal{F}_L = {u,v,w}$

• $u = (P_1,S_1) = (\Sigma^\ast ab \Sigma^\ast \cup \Sigma^\ast a, \Sigma^\ast ab \Sigma^\ast \cup b\Sigma^\ast)$
• et$v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$
• $w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

Sommaire

Pour résumer (comme vous demandiez une procédure simple):

• Pour le calcul des décompositions d'une langue , on calcule d' abord les quotients gauche de L .$L$$L$
• Vous pouvez le faire, dans le langage de l'article, en construisant un DFA minimal pour L puis pour chaque état q dans A (correspondant, en tant que classe d'équivalence de Nérode, à un quotient de gauche) calculer l'avenir de q dans A , obtenant ainsi un quotient gauche de la langue pour chaque état.$A$$L$$q$$A$$q$$A$
• La collection de quotients de gauche ainsi obtenue donne, en général, un sous-ensemble des facteurs de droite.$S_R$
• Calculer ensuite la Fermeture -stable de S R , qui peut être fait dans la pratique , en formant l'intersection de tout sous - ensemble de S R et l' ajout d' un sous - ensemble ainsi obtenu à S R .$\cap$$S_R$$S_R$$S_R$
• L'ensemble en même temps que toutes les intersections de l'étape précédente est alors l'ensemble des facteurs de droite L .$S_R$$L$
• Afin d'obtenir les facteurs de gauche, on peut calculer les quotients de droite .$L$
• Ce sont des ensembles de la forme , pour y ∈ Σ ∗ . Maintenant, ce ne sont encore qu'un nombre fini, et pour x ≠ y , nous avons L y - 1 = L x - 1 si et seulement si pour tout u ∈ Σ ∗ , u x ∈ L ⇔ u y ∈ L , c'est-à-dire peut être préfixé aux mots de la langue avec exactement le même ensemble de chaînes.$Ly^{-1}$$y\in \Sigma^\ast$$x\neq y$$Ly^{-1} = Lx^{-1}$$u\in \Sigma^\ast$$ux \in L \Leftrightarrow uy \in L$
• Pour calculer , considérons ces états q dans A tels que x soit contenu dans l'avenir de q . L'union du passé de ces États constitue un bon quotient. Retrouvez tous ces quotients.$Lx^{-1}$$q$$A$$x$$q$
• Vous savez que vous avez terminé lorsque vous avez trouvé autant de facteurs de gauche que de bons facteurs.
• Trouvez les paires de facteurs à gauche et à droite tels que X ⋅ Y ⊆ L . Ceci est F L .$X,Y$$X\cdot Y \subseteq L$$\mathcal{F}_L$

1. The Universal Automaton de Lombardy et Sakarovitch (dans Texts in Logic and Games, Vol 2: Logic and Automata: History and Perspectives , 2007)