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

10

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.

zic10
fuente

Respuestas:

17

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:Lpags

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 .wpagsw=XyzEl |XyEl |pagsEl |yEl |1XyyozLyo0 0

Puede usar esta caracterización para demostrar que el idioma requiere estados p + 1 .{0 0pags}pags+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 + 1X,yLzXzLyzLpagsLpagsL={0 0pags}pags+1palabras desiguales por pares, a saber, .ϵ,0 0,...,0 0pags

Yuval Filmus
fuente
Sí, zpuede estar ^vacío, pero creo que tiene un error tipográfico en su presupuesto. xy^i ∈ L debería serxy^i z ∈ L
Grijesh Chauhan
12

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 ).pagspags+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
Buena respuesta: explica mucho sin dar la solución a lo que parece un ejercicio de tarea. Bienvenido a la informática !
David Richerby
1

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.un3unun3

vonbrand
fuente
-2

¡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 .

vzn
fuente
norte
nortenorte+1
@Yuval a la derecha. creo que esta idea puede funcionar, pero tal vez no tenga los detalles exactamente correctos, los detalles son complicados, supongo que podría estar en algún lugar de la literatura pero no la
he