¿Cómo determinar si un idioma es recursivo o recursivo enumerable?

Question

Tengo que determinar si un idioma (por ejemplo L = {a^nb^mc^s | 0 < = n < = m < = s}) es regular, sin contexto, recursivo, recursivamente enumerable o ninguno de ellos .

Sé cómo determinar si un idioma es regular (encuentra un DFA o una expresión regular que funciona) o sin contexto (encuentre una PDA o gramática sin contexto que funcione); Sé que un lenguaje recursivo tiene una máquina de Turing que siempre se detiene y que un lenguaje recursivo enumerable tiene una máquina de Turing que no puede detenerse.

Entonces la pregunta es: ¿hay un criterio rápido para determinar si el idioma es recursivo o recursivamente enumerable o ninguno? Por ejemplo, no tengo que construir un PDA para comprender que un idioma no tiene contexto, no lo puedo ver porque requiere una pila; ¿Hay un acercamiento rápido similar al problema (que afortunadamente ahorra el problema de construir una máquina de Turing)?

Answer 1

No hay una forma estructural de verificar si un idioma es recursivo versus recursivamente enumerable. En realidad, hay una prueba muy buena que dice que para cualquier autómata capaz de reconocer los lenguajes recursivos, hay al menos un lenguaje RE no en R que el autómata también acepta; es una variante del argumento de diagonalización que usa para mostrar la existencia de problemas indecidibles.

La principal manera de demostrar que un lenguaje está en RE pero no en R es probar que el lenguaje está en RE (quizás definiendo una TM para él), luego reducir un problema conocido en RE pero no R en eso problema. Por ejemplo, si puede demostrar que cualquier instancia del problema de detención puede resolverse transformándola en una instancia de su problema, usted sabe que no puede tener una solución recursiva, y si continúa con una TM para el idioma que usted sabe que el idioma está en RE. Juntos, tiene un lenguaje en RE pero no R.

Answer 2

Para un lenguaje sin contexto un método rápido es solo ver el número de comparaciones.
En el ejemplo, vea n<=m y m<=s. Entonces hay dos comparaciones involucradas. Entonces puedes sacarlo simplemente diciendo que no está libre de contexto. Si hay una sola comparación involucrada, llámela como un lenguaje libre de contexto.

Igual es el caso con los idiomas regulares. No debe haber relación entre las dos variables, quiero decir que no debe haber ningún tipo de comparación. Por ejemplo, considere los idiomas: 0^m+n 1^n 0^m. Observe con cuidado que solo se ha realizado una comparación que es m+n = n+m (presionar y soltar los símbolos). Por lo tanto, no tiene ningún contexto.
Ahora vea 0^n+m 1^n+m 0^m vea claramente la comparación entre los primeros 2 y los dos siguientes.

Me tomé un tiempo para resolverlo. Pero tomará algunos para tomar las decisiones. Créeme, realmente funciona. Aquí está el último ejemplo para el lenguaje regular. a^n b^2m es regular (Ver no hay comparaciones entre n y m) y {a^n b^m |n=2m} es libre de contexto, ya que tiene sólo una comparación (no regular)

Esperanza esto ayuda