Diseñe una máquina de Turing que acepte palabras de longitud impar con uno en el medio
por ejemplo : $00100\in L,\quad 011\in L$ pero $101,11,11011\notin L$
He probado esto:
borre el primer dígito (dígito borrado marcado con x) y luego vaya a la derecha hasta que vea un espacio, cuando pase por el primer espacio (el final de la palabra) borre el primer dígito de la derecha (marcado con y) luego vaya a la izquierda hasta que vea x (bucle)
¿alguna idea?
Tu estrategia de sustituir con x a la izquierda e y a la derecha está bien, pero en algún momento hay que comprobar ese 1 en el medio (y los impares).
Así que: cuando vuelvas a q0 viniendo de q3, y veas una y, entonces debes haber tenido una cadena de longitud par, por lo que entonces debes rechazar.
Además: viniendo de q0: si ves un 0 debes ir a un estado diferente que si ves un 1, porque ese 0 o 1 podría ser el símbolo del medio. Así que: si después de sustituir ese 0 o 1 por una x, y ves una y (o un espacio, en caso de que tu cadena fuera un solo símbolo) a la derecha de la misma, entonces debes detenerte, y aceptar o rechazar dependiendo de si acabas de sustituir un 1 o un 0 (por eso necesitas dos estados diferentes.
Aquí hay una máquina actualizada:
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
