Myhill-Nerode e propriedades de fechamento

É sabido que as línguas regulares são caracterizadas pela equivalência Myhill-Nerode. Para o idioma$L$ sobre $\Sigma^*$ defina a equivalência $x\sim_L y$ sobre $\Sigma^*$ iff para todos $z\in\Sigma^*$ temos $xz\in L \iff yz\in L$. Então$L$ é regular se $\sim_L$ é de índice finito, ou seja, possui um número finito de classes de equivalência.

Eu sei que a relação pode ser usada para mostrar que alguns idiomas não são regulares, indicando infinitamente muitas seqüências que não são equivalentes.

Minha pergunta: podemos usar facilmente o Myhill-Nerode para mostrar propriedades de fechamento de idiomas comuns? Ou devemos usar a "congruência sintática" das línguas?

Como exemplo de prefixo, é fácil, pois $x\sim_L y$ implica $x\sim_{\mbox{pref}(L)} y$. Mas como lidamos com sufixo, concatenação, estrela, espelho?

Eu faço o fechamento em operações booleanas com a caracterização MyHill-Nerode. Nunca vi isso assim. Uma congruência correta$\sim$ satura um idioma $L$ E se

$$u \sim v \Rightarrow ( u \in L \leftrightarrow v \in L )$$ ou equivalentemente se $L$é uma união de classes de congruência. Nós usamos:

Teorema: (MyHill-Nerode) Uma linguagem é regular se e somente se houver uma congruência correta de índice finito que satura$L$.

Agora, suponha que tenhamos idiomas regulares $L_1, L_2 \subseteq X^{\ast}$e denotar $\sim_{L_1}, \sim_{L_2}$algumas congruências corretas de índice finito saturando-as. Então

$$u \sim v :\Leftrightarrow u \sim_{L_1} v \land u \sim_{L_2} v$$ é uma congruência correta (a interseção de ambos) e refina os dois. Além disso, temos $$[u]_{\sim} = [u]_{\sim_{L_1}} \cap [u]_{\sim_{L_2}}.$$ Portanto, temos um número finito de classes de equivalência. Isso também indica que a interseção de classes de equivalência$[u]_{\sim_{L_1}}$ e $[v]_{\sim_{L_2}}$ está vazio ou tem um elemento comum $w$ e, portanto, é igual à classe de equivalência $[w]_{\sim}$. Isso dá que$L_1 \cap L_2$ está vazio ou pode ser escrito como a união da classe de equivalência para $\sim$. Pelo teorema acima$L_1 \cap L_2$ é regular.

Para $L_1 \cup L_2$ é uma união de classes de equivalência para $\sim_1$ e $\sim_2$, que são as doze uniões de classes de equivalência para $\sim$, portanto, também é regular. E, para complementação, segue como a partição de classes de equivalência$X^{\ast}$, portanto, uma congruência correta trabalhando para $L_1$ trabalha também para $X^{\ast} \setminus L_1$. $\square$

Comentários adicionais: Na sua pergunta, você também mencionou a congruência correta de Nerode canônica

$$u \equiv_L v :\Leftrightarrow (\forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L)$$ com $L \subseteq X^{\ast}$. Esta é a mais grossa congruência direita saturando$L$. Agora talvez seja natural perguntar se podemos construir a congruência correta de Nerode de$L_1 \cap L_2$ ou $L_1 \cup L_2$ facilmente fora daqueles para $L_1, L_2$, ou se a congruência resultante da interseção surgir como alguma congruência correta de Nerode. Talvez possamos encontrar fórmulas simples como $$u \equiv_{L_1\cap L_2} v \Leftrightarrow u \equiv_{L_1} v \land u \equiv_{L_2} v.$$ Mas o acima não se aplica. E que eu saiba, não existe nenhuma relação simples. Por exemplo, considere$L_1 = (aa)^{\ast}$ e $L_2 = a(aa)^+$, então nós temos $$L_1 \cap L_2 = \emptyset, \qquad L_1 \cup L_2 = X^{\ast} \setminus \{a\}.$$ Agora $\equiv_{L_1} \cap \equiv_{L_2}$ possui pelo menos quatro classes de congruência, pois refina $\equiv_{L_2}$que tem exatamente quatro classes de congruência. Mas$\emptyset$ tem precisamente uma classe e $X^{\ast} \setminus \{a\}$ possui três (todos podem ser vistos facilmente usando o mínimo de autômatos completos).

EDIT (2019.08.18). A operação de espelho e sufixo está relacionada à congruência esquerda

$$u \equiv^L v \Leftrightarrow \forall w \in X^* : wu \in L \leftrightarrow wv \in L.$$ E se $\equiv^L$ tem índice finito, semelhante ao da operação de prefixo e congruência correta, $\equiv^{\operatorname{suffix}(L)}$tem índice finito. E $u \equiv_L v$ iff $\operatorname{mirror}(u) \equiv^{\operatorname{mirror}(L)} \operatorname{mirror}(v)$; e como a operação de espelho é uma bijeção em$X^*$ a última equação dá isso $\equiv^{\operatorname{mirror}(L)}$ tem índice finito iff $\equiv_L$ tem índice finito (observe que a congruência esquerda tem o mesmo índice que a congruência correta para as palavras espelhadas, mas, em geral, uma congruência correta para $\operatorname{mirror}(L)$ pode ter muito mais classes exponenciais, como é mostrado por controles padrão da teoria dos autômatos).

Portanto, essas operações são tratadas se pudermos mostrar que ambas as congruências têm índice finito ao mesmo tempo ou não. Para isso, vamos olhar para a congruência sintática

$$u \equiv_{S(L)} v \Leftrightarrow \forall x,y \in X^* : xuy \in L \Leftrightarrow xvy \in L.$$ Essa congruência refina as duas congruências acima, portanto, se é finita, ambas as congruências acima também são finitas. Isto é$u \equiv_{S(L)} v$ iff para todos $w \in X^*$ temos $[wu]_{\equiv_L} = [wv]_{\equiv_L}$, portanto, temos um mapa bem definido e injetivo do $\equiv_{S(L)}$classes de equivalência às transformações em $\{ [w]_{\equiv_L} : w \in X^* \}$, e se o último for um conjunto finito, o conjunto dessas transformações também será finito, o que implica que $\equiv_{S(L)}$é de índice finito. Então, no total, temos isso$\equiv^L$ tem índice finito se $\equiv_L$ tem índice finito, o inverso é implícito similar.

As classes de equivalência da relação Myhill-Nerode também são os estados do DFA mínimo para o idioma. Portanto, o que for fácil de mostrar usando os DFAs, você poderá converter para uma prova que use o ponto de vista Myhill-Nerode. Onde quer que você precise de NFAs, pode esperar que a prova fique mais complicada.

Mas a resposta correta é: experimente você mesmo! É assim que a pesquisa é feita.