Encontrar la factorización máxima de los idiomas regulares

Deje que el lenguaje sea ​​regular.$\mathcal{L} \subseteq \Sigma^*$

Una factorización de es un par máximo ( X , Y ) de conjuntos de palabras con$\mathcal{L}$$(X,Y)$

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

donde | x ∈ X , y ∈ Y } .$X \cdot Y = \{xy$$x \in X, y \in Y\}$

es máximo si para cada par ( X ′ , Y ′ ) ≠ ( X , Y ) con X ′ ⋅ Y ′ ⊆ L ya sea X ⊈ X ′ o Y ⊈ Y ′ .$(X,Y)$$(X',Y') \neq (X,Y)$$X'\cdot Y' \subseteq \mathcal{L}$$X \not \subseteq X'$$Y \not \subseteq Y'$

¿Existe un procedimiento simple para descubrir qué pares son máximos?

Ejemplo:

Deje . Se calcula el conjunto F = { u , v , w } :$\mathcal{L} = \Sigma^∗ab \Sigma^∗$$F = \{u, v, w\}$

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

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

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

donde .$\Sigma = \{a,b\}$

Otro ejemplo:

y L = Σ * un Σ Factorización establece F = { q , r , s , t } con$\Sigma = \{a, b\}$$\mathcal{L} = \Sigma^*a\Sigma$$F = \{q, r, s, t\}$

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

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

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

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

Como se sugiere en los comentarios a la pregunta, intentaré dar una respuesta (lamentablemente parcial) a la pregunta, al menos en la medida en que haya entendido el problema por mí mismo (esto implica que es posible que encuentre errores, y si encuentra una manera de explicar de manera más breve o clara uno de los siguientes puntos, siéntase libre de editar la respuesta en consecuencia):

Primero, uno debe notar que en realidad no tenemos que calcular el autómata universal de un idioma si queremos calcular las factorizaciones de un idioma.

Del artículo mencionado en mi comentario ¹, hay una correspondencia 1-1 entre los factores izquierdo y derecho de un idioma regular, es decir, dado un factor izquierdo del idioma, el factor derecho correspondiente se determina de manera única y viceversa. Más precisamente, tenemos lo siguiente:

Deje que ser una factorización de L . Entonces Y = ⋂ x ∈ X x - 1 L , X = ⋂ y ∈ Y L y - 1 , es decir, cualquier factor izquierdo es una intersección de los cocientes derechos, y cualquier factor derecho es una intersección de los cocientes izquierdos. A la inversa, cualquier intersección de los cocientes izquierdos de L es un factor derecha de L , y cualquier intersección de cocientes adecuados de L es un factor izquierda de L .$(X,Y)$$L$

Tenga en cuenta que para un lenguaje normal, solo hay un conjunto finito de cocientes izquierdo y derecho y, por lo tanto, el problema se reduce a calcular los cocientes izquierdo y derecho de un idioma, y ​​luego calcular su cierre estable , es decir, un mínimo superconjunto de los cocientes que se cierra bajo intersección. Estos son, precisamente, a continuación, los factores de la derecha y la izquierda factores, y luego por lo general es fácil ver por qué pares son subconjuntos de L .$\cap$$L$

Ejemplo

Para ilustrar los puntos anteriores, considere el primer ejemplo en la pregunta (de la cual también creo que es incorrecto en el documento):

Deje . Ahora, los cocientes izquierdos de L son los conjuntos x - 1 L para x ∈ Σ * , es decir, esas palabras u en Σ * que puede ser prefijado con x , es decir, x u ∈ L . ¿Cuándo es y - 1 L = x - 1 L para distintas x , y ? Este es el caso si y solo 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$y puede ser aumentada a las palabras en L con exactamente los mismos sufijos. Esto significa que, para ponerlo en términos más familiares, son equivalentes a Nerode, y los sufijos necesarios para agregar palabras a una clase de Nerode son precisamente los cocientes izquierdos respectivos.$y$$L$

Para , vemos que nuestras clases de equivalencia de Nerode son$L$

• , el conjunto de palabras que no contiene una b como factor y que termina con a , $N_1$$ab$$a$
• , el conjunto de palabras que termina con b y no contiene una b como factor, y $N_2$$b$$ab$
• , el conjunto de palabras que contiene una b como factor, es decir, N 3 = $N_3$$ab$$N_3 = L$

Se pueden aumentar con los siguientes conjuntos (es decir, estos son los cocientes izquierdos de las palabras en las clases respectivas):

• para x en N 1 consta de todas las palabras en L (cualquier palabra se puede aumentar con una palabra que contenga a b como factor y, por lo tanto, se convierte en una palabra en L ) y b Σ ∗ , es decir 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$
• para x en N 2 es el lenguaje en sí, es decir, S 2 = L y$S_2 = x^{-1}L$$x$$N_2$$S_2 = L$
• para x en N 3 es obviamente Σ ∗ . Es decir, hemos encontrado tres factores de la derecha de L . Como S 2 ⊂ S 1 ⊂ S 3 , sucierre estable ∩ es trivial S 1 , S 2 , S 3 , y esos son precisamente los factores correctos.$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}$

$\mathcal{F}_L$$(P_1,S_1),(P_2,S_2),(P_3,S_3)$.

Ahora, para los factores izquierdos $P_i$, we use the equations of the beginning of this answer:

$P_1$$L \cup \Sigma^\ast a$$P_2$$\Sigma^\ast$$P_3$, we obtain $L$. You can see this by inspection (the most popular excuse for being too lazy to state a formal proof) or by explicitly computing the right quotients (which is fairly analogous, although not completely, to computing the left quotients). Our factorizations are thus given by $\mathcal{F}_L = {u,v,w}$ where

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

Summary

To summarize (as you were asking for a simple procedure):

• For computing the factorizations of a language $L$, first compute the left quotients of $L$.
• You can do so, in the language of the paper, by constructing a minimal DFA $A$ for $L$ and then for each state $q$ in $A$ (corresponding, as a Nerode-equivalence class, to a left quotient) compute the future of $q$ in $A$, thus obtaining one left quotient of the language for each state.
• The collection of left quotients obtained in this way yields, in general, a subset $S_R$ of the right factors.
• Compute then the $\cap$-stable closure of $S_R$, which can be done in practice by forming the intersection of any subset of $S_R$ and adding any subset obtained in this way to $S_R$.
• The set $S_R$ together with all the intersections from the previous step is then the set of right factors of $L$.
• In order to obtain the left factors, we can compute the right quotients of $L$.
• These are sets of the form $Ly^{-1}$, for $y\in \Sigma^\ast$. Now, these are again only finitely many, and for $x\neq y$, we have $Ly^{-1} = Lx^{-1}$ if and only if for all $u\in \Sigma^\ast$, $ux \in L \Leftrightarrow uy \in L$, that is they can be prefixed to words in the language with precisely the same set of strings.
• To compute $Lx^{-1}$, consider those states $q$ in $A$ such that $x$ is contained in the future of $q$. The union of the pasts of those states constitute one right quotient. Find all these quotients.
• You know you are done when you have found as many left factors as you have right factors.
• Find those pairs of left and right factors $X,Y$ such that $X\cdot Y \subseteq L$. This is $\mathcal{F}_L$.

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