Defina a equivalência de Nerode sobre um idioma como iff para cada .$L \subseteq \Sigma^{*}$$u \sim_L v$$uw \in L \Leftrightarrow vw \in L$$w \in \Sigma^{*}$

A equivalência Nerode possui finitas classes de equivalência precisamente quando pode ser reconhecido por um autômato de estado finito. Este é o teorema de Myhill-Nerode .${\sim}_L$$L$

Existe uma caracterização semelhante de linguagens sem contexto?

Motivação:

As classes de equivalência Nerode cada um, corresponder a um estado distinto em qualquer autómato que reconhece . Cada CFL pode ser reconhecida por um NPDA, que possui um número finito de estados, mas também uma pilha potencialmente ilimitada de símbolos do alfabeto. A pilha controla uma maneira possível de analisar uma string. O número de classes de equivalência pode ser infinito, pois a pilha pode armazenar um número ilimitado de símbolos.$L$

Estou perguntando: sempre há uma maneira de agrupar classes de equivalência para que cada grupo represente um estado do PDA, com cada classe dentro do agrupamento representando estados equivalentes da pilha para esse estado do PDA?

Por exemplo, o idioma dos parênteses aninhados corretamente precisa apenas dos estados para manipular pope push, como a pilha acompanhará a profundidade atual do aninhamento. Se esse agrupamento sempre pode ser realizado, se o número de agrupamentos é finito determina se o idioma é livre de contexto.

Como apontado por @sdcvvc em um comentário, uma forma desta pergunta foi feita como /math/118362, embora a resposta de Yuval Filmus à pergunta relacionada em Exemplo de uma linguagem livre de contexto que não obstante PODE ser bombeado? é mais relevante.

David S. Wise fornece em seu artigo Um forte lema de bombeamento para linguagens livres de contexto, um forte lema de bombeamento equivalente a ser livre de contexto. Ele também fornece uma condição equivalente adicional (propriedade 3 na página 362) que, segundo ele, pode ser vista como um análogo do teorema de Myhill-Nerode. Como aplicação deste último, ele mostra que$\{ a^nba^{mn} : m,n > 0 \}$ não pode ser expresso como uma interseção finita de linguagens sem contexto.

Mais informações sobre o forte lema de bombeamento aparecem em uma das minhas respostas .

Há uma caracterização muito boa de linguagens livres de contexto (creditadas a Wechler) no artigo de Berstel e Boasson, Para uma teoria algébrica das linguagens livres de contexto . Deixe-me apresentar algumas definições para declarar esse resultado (Teorema 3.1 do artigo).

O fechamento polinomial $Pol(\mathcal{L})$ de uma classe $\mathcal{L}$ de línguas de $A^*$ é o conjunto de todos os idiomas que são uniões finitas de produtos da forma $L_0a_1L_1 \dotsm a_nL_n$, Onde $L_0, ..., L_n \in \mathcal{L}$ e $a_1, ..., a_n \in A$.

Uma álgebra é uma classe$\mathcal{A}$ de idiomas que contêm o idioma $\{1\}$ e tal que $\mathcal{A} = Pol(\mathcal{A})$. É gerado finitamente se$\mathcal{A} = Pol(\mathcal{F})$ para algum conjunto finito $\mathcal{F}$de idiomas. É estável se, para cada$L \in \mathcal{A}$ e $u \in A^*$, o idioma $u^{-1}L = \{v \mid uv \in L\}$ também pertence a $\mathcal{A}$. Note que basta ter$a^{-1}L \in \mathcal{A}$ para todos $a \in A$.

Teorema . Uma linguagem de$A^*$ é livre de contexto se e somente se pertencer a uma álgebra estável finitamente gerada.

Veja o artigo para exemplos ilustrativos e muitas consequências interessantes.