¿Es posible construir DFA para palabras de longitud impar con 1 en el medio?

8

L:={w{0,1}|la longitud de es impar 1 está en el medio deww}

Entonces el alfabeto es . Mi problema es que no puedo hacer un seguimiento de la igualdad de caracteres antes y después de . Un DFA limitado para la longitud inferior a 6:{0,1}1ingrese la descripción de la imagen aquí

¿Cómo puedo expandirlo para que acepte palabras largas? ¿Es posible?

Intenté poner ciclos en él, pero como ya dije, simplemente no puedo hacer un seguimiento de la cantidad de caracteres después de para que sea igual a eso antes. En otras palabras, estar siempre en el medio.1

usuario8
fuente

Respuestas:

13

No, no puedes. Prueba mediante lema de bombeo: Suponga que es regular y sea ​​la longitud de bombeo, considere la palabra . Así, hay con y tal . A continuación, .Lnw=0n10nx,y,z{0,1}|xy|<n|y|>0xyz=wiN0:xyizL

Pero debido a su restricción de longitud, e consisten solo en y todos están antes del . De este modo .xy01xy2z=0n+|y|10nL

Por lo tanto, no es regular y no puede ser expresado por ningún DFA.L

Martin Glauer
fuente