Lenguaje regular no aceptado por DFA que tiene como máximo tres estados

Describa un idioma normal que no pueda ser aceptado por ningún DFA que tenga solo tres estados.

No estoy realmente seguro de por dónde empezar con esto y me preguntaba si alguien podría darme algunos consejos o sugerencias. Entiendo que el lema de bombeo se puede usar para probar que un idioma no es regular, pero en este caso, debería ser un idioma regular. Si alguien tiene alguna idea, se lo agradeceríamos.

Se puede afirmar que el lema de bombeo tiene en cuenta el número de estados en el DFA. Cada lenguaje aceptado por un DFA con p estados satisface el siguiente lema de bombeo:$L$$p$

Cada palabra de longitud al menos p se puede dividir como w = x y z , donde | x y | ≤ p y | y | ≥ 1 , de modo que x y i z ∈ L para todo i ≥ 0 .$w$$p$$w=xyz$$|xy| \leq p$$|y| \geq 1$$xy^iz \in L$$i \geq 0$

Puede usar esta caracterización para demostrar que el idioma requiere estados p + 1 .$\{0^p\}$$p+1$

Otro método es usar el teorema de Myhill - Nerode. Dos palabras son equivalentes (con respecto a algún lenguaje L ) si para alguna palabra z , x z ∈ L e y z ∉ L o al revés. El teorema de Myhill - Nerode establece que si hay p palabras no equitativas por pares, entonces cada DFA para L tiene al menos p estados. Para el ejemplo L = { 0 p } , puede encontrar p + $x,y$$L$$z$$xz \in L$$yz \notin L$$p$$L$$p$$L = \{0^p\}$$p+1$palabras desiguales por pares, a saber, .$\epsilon,0,\ldots,0^p$

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 ).$p$$p+1$$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)

Hay un algoritmo para minimizar los DFA. Simplemente elija un idioma que tenga un DFA mínimo de 4 (o más) estados. Cualquier cosa que tenga una longitud mínima de 3 símbolos servirá, es decir, el lenguaje de la expresión regular , o (aún más simple) a 3 . Para ver por qué, eche un vistazo a la prueba del lema de bombeo para los idiomas normales.$a^3 a^*$$a^3$

¡Otra idea, la diagonalización ! enumere todos los DFA de 3 o menos estados, tome la unión de todos ellos y luego tome el complemento. Este es un DFA por cierre de operaciones de lenguaje regular. Esto podría construirse a través de un algoritmo, pero la pregunta solo pide una descripción .