Prueba de no regularidad, basada en la complejidad de Kolmogorov

8

En clase, nuestro profesor nos mostró 3 métodos para probar la no regularidad:

  1. Teorema de Myhill-Nerode
  2. Lema de bombeo para idiomas regulares
  3. 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 L(Σbool) Lx={y(Σbool)|xyL} x(Σbool) c x,y(Σbool)

 K(y)log2(n+1)+c

if es la enésima palabra en el idioma . y Lx

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!

gammaALpha
fuente

Respuestas:

8

Que yo sepa, este no es uno de los enfoques "clásicos" utilizados para caracterizar los idiomas regulares.

Este enfoque se discute en "Un nuevo enfoque para la teoría del lenguaje formal por la complejidad de Kolmogorov" , por Ming Li y Paul MB Vitanyi (ver sección 3.1).

Dan varios ejemplos donde uno puede usar la declaración que mencionó en lugar de usar el lema de bombeo. Por ejemplo, demostrando la no regularidad de dondeL

L={1p|p is prime} .

Dados algunos , . Elijamos donde es la 'ésima prima. Deje ser la primera palabra en . Obviamente, donde es el primo . De acuerdo con el enunciado que mencionó, ( ), para algunas constantes dependen solo de (consulte el documento).xΣLx={y|xy=1pp is prime}x=1ppky1Lxy1=1pppk+1K(y1)cn=1cL

Como esto es válido para todas las , podemos vincular la complejidad de Kolmogorov de todos los elementos en por la misma constante . Sin embargo, vimos que realidad consiste en diferencias entre primos consecutivos, es decir, donde es la 'ésima prima. Como sabemos que no puede haber limitado la complejidad de Kolmogorov (las diferencias primarias se vuelven arbitrariamente grandes), esto significa que no puede ser regular.xS={y1x|x=1p for prime p y1x is the first string in Lx}cSS={1pk+1pk|k1}pkkSL

Ariel
fuente
2
No sabía de esta técnica. ¿Te apetece agregar una respuesta a nuestra pregunta de referencia ?
Raphael
1
Sí, puedo agregar uno más tarde. Sin embargo, debo admitir que yo tampoco estaba al tanto de esta técnica, acabo de encontrar este artículo después de buscar la pregunta de op. No estoy seguro de cuán popular (en relación con otros métodos) resultó ser esta técnica. El artículo en Arxiv fue publicado en SIAM en 1995, por lo que no es tan nuevo como pensé al principio (enfoque aún, interesante y original).
Ariel
Muchas gracias por el esfuerzo y el ejemplo. ¿Podría explicarme por qué es la primera palabra en ? p es el k-ésimo y p 'es el k + 1 primo, entonces ¿no deberíamos decir que ? Y como entendí, pp 'no necesita ser necesariamente primo, ¿por eso elegimos esto?  1pp Lx y1=1pp
gammaALpha
1
El prefijo es , la primera palabra en con el prefijo es modo que es el siguiente primo, entonces . Elegimos de esta manera porque esto nos permite limitar la complejidad de Kolmogorov de todos estos por una constante. Como las diferencias principales pueden ser arbitrariamente grandes, el conjunto de todos estos es infinito (por lo que no puede tener una complejidad limitada). Agregué una respuesta a la pregunta de referencia, contiene más información que puede encontrar útil y otro ejemplo. x=1pLxy1x=1pppxy1x=1p+(pp)=1pxy1xy1x
Ariel
3

Otro ejemplo muy fácil es el siguiente: use la complejidad de Kolmogorov para demostrar que no es regular.Lww={www{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 .DLDx=yzyxLDz

Ahora suponga que es regular; entonces hay un DFA que lo reconoce.LwwDww

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=yzyDwwqizx=yzyz=ww

 Let y = 10110
       y   z
 x = 10110 0  >> rejected
 x = 10110 1  >> accepted  (w=101, |y|>|z|)
 x = 10110 00 >> rejected
 x = 10110 01 >> rejected
 ....
 x = 10110 10110 >> accepted  (w=10110,  |y|=|z| !!!)
 ....
 x = 10110 1101101 >> accepted (w=101101, |z|<|y|

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 .Dwwqiy|y|Dww2|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|Dwwlogiqilogyyc

podemos "reconstruir" la cadena ; pero para lo suficientemente grande tenemoslo cual es una contradicción porque es incompresible.yy<|y|y

Vor
fuente
No sabía de esta técnica. ¿Te apetece agregar una respuesta a nuestra pregunta de referencia ?
Raphael