Mt generadora(con multicinta)
Hemos optado por una MT multicinta porque de esta forma podemos utilizar una cinta de trabajo, donde realizaremos las operaciones pertinentes para ir generando las cadenas y otra cinta que será la de salida y que es donde iremos escribiendo todas las cadenas que vamos generando.
Idea: En principio partimos de dos cintas que solo contienen blancos. En la cinta de trabajo iremos escribiendo ceros y por cada cero que escribimos en la cinta de trabajo escribimos un a^nb^2na^n siendo n igual al número de ceros que hay en la cinta de trabajo.Las cadenas que vamos escribiendo en la cinta de salida están separadas por #.
El funcionamiento de la MT es bastante sencillo en q0 y q1 se escribe en la cinta de salida la cadena vacía.Luego se escribe el primer cero en la cinta de trabajo y empiezan las operaciones.Primero se sitúa el cabezal al comienzo de la cinta (q2). Después se recorre la cinta de trabajo hacia la derecha y se escriben en la cinta de salida el número de a's en proporción al de ceros de la cinta de trabajo(q3).Luego se recorre hacia la izquierda y se escriben las b's (q4, q5).Por último se vuelve a recorrer la cinta de trabajo hacia la derecha y se vuelve a escribir las a's(q6).Para poder generar más cadenas se tiene que incrementar el número de ceros de la cinta de trabajo por eso en q1 se incrementa en uno el número de ceros.Al poner este cero el cabezal no se queda en el principio de la cadena por eso en q2 lo que hacemos es situarlo al principio de la cadena de 0's para poder comenzar a hacer el recorrido de izquierda a derecha y por lo tanto la escritura de nuevas cadenas.
2 comentarios:
Llega un momento en que nos quedamos atascados en el estado q4 escribiendo b´s en la cinta de salida sin parar (f(q4,{0,B})=(q4,{0,L},{b,R})). En este punto tendríamos que movernos hacia la izquierda y escribir tantas b´s como ceros.
Si, he tenido un despiste al copiarla. Realmente allí va la transición f(q4{0,B})=(q5{0,L},{b,R}). El estado q5 es el que se encarga de desplazar el cabezal a la izquierda y de limitar el número de b's, tal y como estaba copiada la MT no entraba nunca en el estado q5. Ahora lo rectificaré.
Publicar un comentario