Encontrar fatoração máxima de idiomas regulares

Vamos linguagem $\mathcal{L} \subseteq \Sigma^*$ ser regular.

Uma fatoração de $\mathcal{L}$ é um par máximo $(X,Y)$ de conjuntos de palavras com

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

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

$(X,Y)$$(X',Y') \neq (X,Y)$$X'\cdot Y' \subseteq \mathcal{L}$$X \not \subseteq X'$$Y \not \subseteq Y'$

Existe um procedimento simples para descobrir quais pares são máximos?

Exemplo:

Seja . O conjunto é calculado:$\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^∗)$

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

Outro exemplo:

L = Σ * um Σ F = { q , r , s , t $\Sigma = \{a, b\}$ e Conjunto de fatoração com$\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})$

Conforme sugerido nos comentários da pergunta, tentarei dar uma resposta (infelizmente parcial) à pergunta, pelo menos na medida em que eu mesmo entendi o problema (isso implica que você poderá encontrar erros e se encontrar Para explicar de maneira mais rápida ou clara um dos pontos abaixo, fique à vontade para editar a resposta de acordo):

Primeiro, deve-se notar que, na verdade, não precisamos calcular o autômato universal de uma linguagem se queremos calcular as fatorações de uma linguagem.

A partir do papel mencionado no meu comentário ¹, há uma correspondência 1-1 entre fatores esquerdo e direito de uma linguagem regular, isto é, dado um fator esquerdo da língua, o fator de direito correspondente é determinado e vice-versa exclusivamente. Mais precisamente, nós temos o seguidor:

Deixe que ser um fatoração de L . Então Y = ⋂ x ∈ X x - 1 L , X = ⋂ y ∈ Y L y - 1 , ou seja, qualquer fator esquerdo é uma interseção dos quocientes direitos e qualquer fator direito é uma interseção dos quocientes esquerdos. Por outro lado, qualquer intersecção de quocientes esquerda de L é um fator direito de L , e qualquer intersecção de quocientes direito de L é um fator esquerda de L .$(X,Y)$$L$

Observe que, para um idioma comum, existe apenas um conjunto finito de quocientes esquerdo e direito e, portanto, o problema se reduz ao cálculo dos quocientes esquerdo e direito de um idioma e, em seguida, calcula seu fechamento -estável, ou seja, um mínimo superconjunto dos quocientes que são fechados sob interseção. Estes são, então, precisamente os fatores direita e fatores de esquerda, e, em seguida, geralmente é fácil ver quais pares são subconjuntos de L .$\cap$$L$

Exemplo

Para ilustrar os pontos acima, considere o primeiro exemplo da pergunta (do qual também acho incorreto no artigo):

Vamos . Agora, os quocientes esquerda de L são os conjuntos x - 1 L para x ∈ Σ * , isto é, aquelas palavras u em Σ * que podem ser prefixados com x , ou seja, x u ∈ L . Quando y - 1 L = x - 1 L para x distinto , y ? Este é o caso se e somente se $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$e pode ser aumentado para palavras em L com exatamente os mesmos sufixos. Isso significa que, para colocá-lo em termos mais familiares, eles são equivalentes ao Nerode e os sufixos necessários para anexar às palavras em uma classe Nerode são precisamente os respectivos quocientes à esquerda.$y$$L$

Para , vemos que nossas classes de equivalência Nerode são$L$

• , o conjunto de palavras que não contêm a b como fator e terminam em a , $N_1$$ab$$a$
• , o conjunto de palavras que termina com be não contém a b como fator e $N_2$$b$$ab$
• , o conjunto de palavras que contêm a b como fator, ou seja, N 3 = $N_3$$ab$$N_3 = L$

Eles podem ser aumentados com os seguintes conjuntos (ou seja, esses são os quocientes à esquerda das palavras nas respectivas classes):

• para x em N 1 consiste em todas as palavras em L (qualquer palavra pode ser aumentada com uma palavra que contenha a b como fator e assim se torne uma palavra em L ) e b Σ ∗ , que é 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 em N 2 é a própria linguagem, isto é, S 2 = L e$S_2 = x^{-1}L$$x$$N_2$$S_2 = L$
• para x em N 3 é obviamente Σ ∗ . Isto é, nós encontramos três fatores direita de L . Como S 2 ⊂ S 1 ⊂ S 3 , a sua ∩ fecho -stable é trivialmente S 1 , S 2 , S 3 , e aqueles que são, em seguida, precisamente os factores direita.$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}$

Portanto, nosso conjunto de fatoração é da forma ( 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)$

Agora, para os fatores esquerdos , usamos as equações do início desta resposta:$P_i$

.

Para , este rendimentos G ∪ Σ * um , para P 2 obtemos Σ * e para P 3 , obtém-se L . Você pode ver isso inspecionando (a desculpa mais popular por ser muito preguiçoso para apresentar uma prova formal) ou calculando explicitamente os quocientes certos (o que é bastante análogo, embora não completamente, ao cálculo dos quocientes esquerdos). Nossas fatorações são assim dadas por F L = u , v , w onde$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)$
• e$v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$
• $w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

Sumário

Para resumir (como você estava solicitando um procedimento simples):

• Para computar os fatorações de uma linguagem , em primeiro lugar calcular os quocientes esquerda de L .$L$$L$
• Você pode fazer isso, no idioma do artigo, construindo um DFA mínimo para L e, em seguida, para cada estado q em A (correspondente, como uma classe de equivalência de Nerode, a um quociente esquerdo), calcule o futuro de q em A , obtendo assim um quociente esquerdo do idioma para cada estado.$A$$L$$q$$A$$q$$A$
• A recolha de quocientes deixadas obtidos deste modo os rendimentos, em geral, um subconjunto dos factores direita.$S_R$
• Computação, em seguida, o fecho -stable de S R , que pode ser feito na prática pela formação da intersecção de qualquer subconjunto de S R e adicionando qualquer subconjunto obtido desta maneira para S R .$\cap$$S_R$$S_R$$S_R$
• O conjunto em conjunto com todas as intersecções da etapa anterior é, em seguida, o conjunto de factores de certas L .$S_R$$L$
• A fim de obter os fatores de esquerda, podemos calcular os quocientes direito de .$L$
• Estes são os conjuntos de forma , para y ∈ Σ * . Agora, estes são novamente apenas finitamente muitos, e para x ≠ y , temos L y - 1 = L x - 1 se e somente se para todos u ∈ Σ ∗ , u x ∈ L ⇔ u y ∈ L , são eles pode ser prefixado para palavras no idioma com exatamente o mesmo conjunto de strings.$Ly^{-1}$$y\in \Sigma^\ast$$x\neq y$$Ly^{-1} = Lx^{-1}$$u\in \Sigma^\ast$$ux \in L \Leftrightarrow uy \in L$
• Para calcular , considere os estados q em A de modo que x esteja contido no futuro de q . A união do passado desses estados constitui um quociente correto. Encontre todos esses quocientes.$Lx^{-1}$$q$$A$$x$$q$
• Você sabe que terminou quando encontrou tantos fatores à esquerda quanto os fatores certos.
• Encontrar os pares de factores direita para a esquerda e de tal modo que X ⋅ Y ⊆ L . Este é F G .$X,Y$$X\cdot Y \subseteq L$$\mathcal{F}_L$

1. O Autômato Universal de Lombardia e Sakarovitch (em Textos em Lógica e Jogos, Vol. 2: Lógica e Automata: História e Perspectivas , 2007)