Defina la equivalencia de Nerode sobre un idioma como iff para cada .$L \subseteq \Sigma^{*}$$u \sim_L v$$uw \in L \Leftrightarrow vw \in L$$w \in \Sigma^{*}$

La equivalencia de Nerode tiene finitamente muchas clases de equivalencia precisamente cuando puede ser reconocido por un autómata de estado finito. Este es el teorema de Myhill-Nerode .${\sim}_L$$L$

¿Existe una caracterización similar de los lenguajes sin contexto?

Motivación:

Las clases de equivalencia Nerode corresponden cada uno a un estado distinto en cualquier autómata que reconoce . Cada CFL puede ser reconocido por un NPDA, que tiene un número finito de estados pero también una pila de símbolos alfabéticos potencialmente ilimitados. La pila realiza un seguimiento de una posible forma en que se puede analizar una cadena. El número de clases de equivalencia puede ser infinito ya que la pila puede almacenar un número ilimitado de símbolos.$L$

Me pregunto: ¿hay siempre una forma de agrupar las clases de equivalencia para que cada grupo represente un estado del PDA, y cada clase dentro del grupo represente estados equivalentes de la pila para ese estado PDA?

Por ejemplo, el lenguaje de paréntesis correctamente anidados solo necesita estados para manejar popy push, ya que la pila hará un seguimiento de la profundidad de anidación actual. Si tal agrupamiento siempre se puede hacer, entonces si el número de agrupamientos es finito determina si el lenguaje está libre de contexto.

Como señaló @sdcvvc en un comentario, se formuló una forma de esta pregunta como /math/118362, aunque la respuesta de Yuval Filmus a la pregunta relacionada en el Ejemplo de un lenguaje sin contexto que no obstante PUEDE ser bombeado? Es más relevante.

David S. Wise proporciona en su documento Un fuerte lema de bombeo para lenguajes sin contexto un fuerte lema de bombeo que es equivalente a estar libre de contexto. También proporciona una condición equivalente adicional (propiedad 3 en la página 362) que, según él, podría verse como un análogo del teorema de Myhill-Nerode. Como aplicación de este último, muestra que no puede expresarse como una intersección finita de lenguajes libres de contexto.$\{ a^nba^{mn} : m,n > 0 \}$

Más información sobre el fuerte lema de bombeo aparece en una de mis respuestas .

Hay una caracterización muy agradable de los lenguajes sin contexto (acreditados a Wechler) en el artículo de Berstel y Boasson, Hacia una teoría algebraica de lenguajes sin contexto . Permítanme presentarles algunas definiciones para establecer este resultado (Teorema 3.1 en el documento).

El cierre polinomial de una clase de idiomas de es el conjunto de todos los idiomas que son uniones finitas de productos de la forma , donde y .$Pol(\mathcal{L})$$\mathcal{L}$$A^*$$L_0a_1L_1 \dotsm a_nL_n$$L_0, ..., L_n \in \mathcal{L}$$a_1, ..., a_n \in A$

Un álgebra es una clase de idiomas que contiene el idioma y tal que . Se genera de manera finita si para algún conjunto finito de idiomas. Es estable si, para cada y , el idioma también pertenece a . Tenga en cuenta que es suficiente para tener para todos .$\mathcal{A}$$\{1\}$$\mathcal{A} = Pol(\mathcal{A})$$\mathcal{A} = Pol(\mathcal{F})$$\mathcal{F}$$L \in \mathcal{A}$$u \in A^*$$u^{-1}L = \{v \mid uv \in L\}$$\mathcal{A}$$a^{-1}L \in \mathcal{A}$$a \in A$

Teorema . Un lenguaje de tiene contexto si y solo si pertenece a un álgebra estable finitamente generada.$A^*$

Vea el artículo para ejemplos ilustrativos y muchas buenas consecuencias.