¿Por qué no se puede decidir la regularidad de un lenguaje sin contexto?

Como he estudiado, decidir la regularidad de los lenguajes libres de contexto es indecidible.

Sin embargo, podemos probar la regularidad utilizando el teorema de Myhill-Nerode que proporciona una condición necesaria y suficiente. Entonces el problema debería ser decidible.

¿Dónde está mi error?

formal-languages computability regular-languages undecidability Jiya
fuente

¿Cómo propones saber si la relación Myhill-Nerode tiene un número finito de clases de equivalencia? ¿Qué propiedad de los lenguajes sin contexto crees que te permite hacer eso?

David Richerby

Verifique la definición de computabilidad: debe proporcionar una máquina de Turing (o, más generalmente, un algoritmo) que resuelva el problema (siempre). Myhill-Nerode es, per se, no un algoritmo, solo una caracterización. ¿La propiedad proporcionada es decidible? ¿Has intentado transformar el teorema en tal algoritmo?

Raphael

@Jiya ¿Qué quieres decir con "decidir la regularidad"? Al principio, parece obvio lo que eso significa, pero en realidad es más sutil. Un procedimiento de decisión (algoritmo) debe tomar una entrada finita, entonces, ¿cómo le daría un lenguaje infinito como entrada? Quizás quieras usar expresiones como

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\ge 0\}$ . OK, pero ¿qué expresiones permitirás?

{a^{n} b^{m} ∣ the m th Turing machine halts on input m}

$\{a^nb^m\mid \text{the }m\text{th Turing machine halts on input }m\}$ ?

{a^{n} b^{k n} ∣ k is one of David Richerby's favourite numbers}

$\{a^nb^{kn}\mid k\text{ is one of David Richerby's favourite numbers}\}$ ?

David Richerby

@Jiya Absolutamente sí. Pero debe elegir qué conjunto de expresiones desea aceptar y escribir una especificación formal de esas expresiones. Luego, su máquina Turing tendría que analizar las expresiones y decidir si corresponden a los idiomas normales o no.

David Richerby

@Jiya Si los únicos idiomas que considera son los del formulario

{a^{k x} b^{ℓ x} c^{m x} | x \geq 0}

$\{a^{kx}b^{\ell x}c^{mx}|x\ge 0\}$ dónde

k

$k$ ,

ℓ

$\ell$ y

m

$m$ son constantes, entonces el lenguaje resultante es regular si, y solo si, dos o tres de

k

$k$ ,

ℓ

$\ell$ y

m

$m$ son cero Entonces, para los idiomas definidos de esa manera, el problema de determinar si el idioma resultante es regular es decidible. Pero, si permite relaciones más complejas entre los números de

a

$a$ s,

b

$b$ s y

c

$c$ s, puede ser indecidible si un idioma es regular. Por eso es de vital importancia cómo se especifican los idiomas.

David Richerby

Respuestas:

Myhill – Nerode proporciona una caracterización de los idiomas regulares, pero eso no es suficiente para mostrar que el problema es decidible. "Decidible" significa que hay un algoritmo (más formalmente, una máquina de Turing) que termina para cada entrada y, por supuesto, siempre da la respuesta correcta. Entonces, en este caso, necesitaría dar un algoritmo que, dado un lenguaje como entrada, determina si la relación Myhill-Nerode tiene un número finito de clases de equivalencia. Resulta que esto no se puede hacer para lenguajes libres de contexto; detalles en su libro de texto de idiomas formales favorito.

Si desea decidir si un lenguaje general es regular, una sutileza adicional es que debe tener cuidado con la entrada de su algoritmo. La entrada debe ser una cadena finita; de lo contrario, incluso solo leer la entrada sería un algoritmo sin terminación. En el caso de los lenguajes sin contexto, puede usar una gramática como representación finita de un lenguaje infinito. Para idiomas más generales, necesitarías ... bueno, algo más general. Sin embargo, en última instancia, si quieres lidiar con todos los idiomas, estás condenado. Sobre cualquier alfabeto finito, hay innumerables idiomas pero solo contablemente muchas cadenas finitas. Eso significa que no puedes describir todos los idiomas usando cadenas finitas. ¹Por lo tanto, intentar escribir un algoritmo para determinar si los lenguajes arbitrarios dados como entrada son regulares en realidad falla antes de que comience. No es solo que no puedas escribir el algoritmo: ¡ni siquiera puedes escribir la entrada!

Tenga en cuenta que esto no significa que usted, un ser humano, no pueda usar Myhill – Nerode para determinar si los idiomas son regulares. Sólo significa que no se puede escribir un conjunto de instrucciones precisas para contar conmigo cómo hacerlo. En algún momento, cualquier conjunto de instrucciones de este tipo tendría que decir algo como "Y luego jugar con eso para ver qué funciona" o "A partir de ahí, debes resolverlo por tu cuenta".

En particular, esto significa que algunos idiomas deben ser indecidibles, ya que hay más idiomas que algoritmos.

David Richerby
fuente

Podemos eludir el problema con la codificación de entrada restringiéndonos a todos los lenguajes recursivamente enumerables, decidibles o incluso libres de contexto. Entonces, tenemos codificaciones de entrada "naturales" (gramáticas, máquinas de Turing, ...) pero aún no podemos decidir la regularidad. Entonces, claramente, hay cosas más sutiles en marcha.

Raphael

Gracias rafael. Lo he editado para aclarar que la sección "fatalidad" se refería a no poder aceptar todos los idiomas como entradas.

David Richerby