Prueba de que

8

Muestra esa L={unanorte2El |norte0 0} no es regular

Hola chicos. Estoy tomando una clase de CS y estas cosas son realmente nuevas para mí, así que tengan paciencia conmigo. Traté de mirar si obtengo alguna contradicción al usar el lema de bombeo para los idiomas normales y lo resolví así:

Suponer Les regular Entonces debe haber un número naturalmetro para todas las palabras z en L con longitud El |zEl |metro y existe una descomposición z=uvw,|uv|m,|v|>0, así que eso u(vi)w está en el idioma para cualquier i0 0.

Considera la cuerda unametro2.

Entonces tuv=unak2=unaX+y, para algunos kmetro y X=(k-1)2.
Entoncesv=unay=una2k-1.

Dejar yo=2. Entoncestu(v2)w=unaX+2y. PeroX+2yno es necesariamente un número natural -> ¡Contradicción! Por lo tanto,L No puede ser regular.

Bueno, sé que este camino es innecesariamente complicado y puedes probarlo de manera diferente (ya conozco la solución más simple). Pero mi pregunta aquí es: ¿es válida también mi prueba o contiene algún defecto? ¿Es formalmente correcto?

Agradezco cualquier comentario! ¡Gracias!

Gilles 'SO- deja de ser malvado'
fuente
1
FYI: las expresiones regulares tal como se definen en informática teórica y las expresiones regulares que usan los programadores están relacionadas, pero son muy diferentes.
2
Parece haber cometido algunos de los errores clásicos al aplicar el lema Pumping. Tenga en cuenta nuestra pregunta de referencia para obtener una explicación detallada y un ejemplo.
Raphael
Esto no es correcto, no. Su argumento no puede depender de asumirtuv=unak2.
Patrick87

Respuestas:

8

No puedes deducir eso tuv=unak2, todo lo que te da el lema de bombeo es que El |tuvEl |metro. No todos los números son menores quemetroson cuadrados No solo eso, sino incluso suponiendo quetuv=unak2, no hay razón para suponer que v=una2k-1; todo lo que el lema de bombeo te da es quevNo está vacío. Finalmente, para obtener una contradicción, no es suficiente queX+2y no necesita ser un cuadrado, no debe ser un cuadrado! Ya queX y X+y son cuadrados adyacentes, en realidad es el caso de que X+2y No es un cuadrado.

Yuval Filmus
fuente
¿Alguna pista sobre cómo arreglar la prueba?
Raphael
El OP "ya sabe [s] la solución más simple", que supongo que equivale a la prueba fija.
Yuval Filmus
@YuvalFilmus No necesariamente. Hay una prueba bastante sencilla usando el teorema de Myhill-Nerode que no tiene nada que ver con el lema de bombeo. Esa podría ser a la que se refiere el OP.
Patrick87