La respuesta de Yuval es genial. Una formulación más simple de lo que ha descrito es que los autómatas finitos no pueden contar arbitrariamente alto, y la cantidad que pueden contar está limitada por los estados numéricos en los autómatas. Más precisamente, para que un autómata cuente hasta , necesita estados p + 1 (un estado sería 0 ).pagsp + 10 0
Esta es, en esencia, toda la idea detrás del lema de bombeo: si una cadena es realmente larga, los autómatas finitos deben "olvidar" qué tan alto se cuenta y comenzar de nuevo, permitiéndole repetir una sección una y otra vez sin que le importe .
Por lo tanto, cualquier lenguaje regular que requiera contar hasta 3 para validar una palabra en él, no puede ser descrito por un autómata finito de tamaño 3.
¿Puedes pensar en ese lenguaje? (Su profesor también puede esperar que pruebe este argumento de conteo, aunque en mi plan de estudios se dio por sentado esta comprensión del lema de bombeo)
Alexis Beingessner
fuente
z
puede estar^
vacío, pero creo que tiene un error tipográfico en su presupuesto.xy^i ∈ L
debería serxy^i z ∈ L