Muestra esa 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 es regular Entonces debe haber un número natural para todas las palabras en con longitud y existe una descomposición , así que eso está en el idioma para cualquier .
Considera la cuerda .
Entonces , para algunos y .
Entonces.Dejar . Entonces. Perono es necesariamente un número natural -> ¡Contradicción! Por lo tanto, 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!
fuente
Respuestas:
No puedes deducir esou v =unak2 , todo lo que te da el lema de bombeo es que El | uv | ≤m . No todos los números son menores quemetro son cuadrados No solo eso, sino incluso suponiendo queu v =unak2 , no hay razón para suponer que v =una2 k - 1 ; todo lo que el lema de bombeo te da es quev No está vacío. Finalmente, para obtener una contradicción, no es suficiente quex + 2 y 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 + 2 y No es un cuadrado.
fuente