Presiona Automata para este lenguaje: la longitud de es impar y su símbolo del medio es 0.

Question

Dale un empujón al autómata para este lenguaje:

{w| the length of w is odd and it's middle symbol is 0}

Aquí está el CFG que escribí para este idioma:

S --> 0|0S0|0s1|1s0|1s1

Esto es lo que he hecho para la parte de la longitud del impar (no estoy usando una pila para la primera parte pero estoy seguro de que necesito usar una pila para la segunda parte):

He pasado días en esta pregunta pero no he tenido suerte,

Answer 1

Una pista amplia: No deberías tener que comprobar que la cuerda tiene la longitud de impar. Ten en cuenta que una cuerda $w$ está en el idioma $L$ descrito anteriormente si se produce la aparición del símbolo $ \mathtt {0}$ en $w$ de tal manera que hay exactamente tantos símbolos en $w$ que apareció antes de que se produjera la $ \mathtt {0}$ como hay después. (Para una pista que es un poco más directa, cada vez que lees un $ \mathtt {0}$ de la cadena no determinar que esta es la correcta, usando la pila para comprobar si la propiedad anterior se mantiene).