En clase, nuestro profesor nos mostró 3 métodos para probar la no regularidad:
- Teorema de Myhill-Nerode
- Lema de bombeo para idiomas regulares
- Prueba de no regularidad, basada en la complejidad de Kolmogorov
Ahora, los dos primeros, el teorema de Myhill-Nerode y el lema de Pumping, lo entendí bien y también pude hacer los ejercicios de los dos primeros métodos. Pero no entendí el tercero. La definición del tercer método es la siguiente:
Deje que sea un lenguaje normal. Let para cada . Entonces existe una constante , tal que para todos
if es la enésima palabra en el idioma .
Ahora no entiendo cómo usar este teorema para demostrar que un lenguaje no es regular, realmente no entiendo el concepto. Utilizamos la complejidad de kolmogorov antes para determinar la longitud del programa de computadora más corto de un objeto. ¿Cómo se prueba la no regularidad con este teorema? ¿Y cuál es el pensamiento detrás de esto?
¡Muchas gracias!
Otro ejemplo muy fácil es el siguiente: use la complejidad de Kolmogorov para demostrar que no es regular.Lww={ww∣w∈{0,1}∗}
Le doy una prueba muy informal con la esperanza de que pueda ayudarlo a comprender mejor el papel de la complejidad de Kolmogorov.
La idea clave es la siguiente: un autómata finito (que reconoce un lenguaje normal ) tiene una cantidad finita de "memoria"; por lo tanto, al ejecutar una cadena de entrada cuando ha "procesado" la primera parte de la entrada la pertenencia de en depende solo de su estado actual y de la segunda parte de la entrada .D LD x=yz y x LD z
Ahora suponga que es regular; entonces hay un DFA que lo reconoce.Lww Dww
Sea una cadena de longitud incompresibley |y|=n≫|D|
Para todas las entradas , al final de la primera parte , el DFA estará claramente en el mismo estado , y por hipótesis solo aceptará si la parte restante es tal que puede dividirse en dos mitades iguales (es decir, ); por ejemplox=yz y Dww qi z x=yz yz=ww
Pero es importante notar que solo hay una cadena de longitudeso es aceptado ( ).z |y| z=y
Entonces, dada la descripción de , el estado al final de , y la longitudpodemos simular el comportamiento de en todas las cadenas y ver cuál acepta ... pero acepta exactamente .Dww qi y |y| Dww 2|y| z=y
Entonces, con un programa de tamañoℓ=|Dww|+logi+logy+c
( se necesita espacio para almacenar la descripción de , espacio para almacenar , espacio para almacenar la longitud de , se necesita espacio para las instrucciones que simulan el DFA )|Dww| Dww logi qi logy y c
podemos "reconstruir" la cadena ; pero para lo suficientemente grande tenemoslo cual es una contradicción porque es incompresible.y y ℓ<|y| y
fuente