Para realizar este generador, vamos a utilizar un MT multicinta con 2 cintas.
La primera sera una cinta con el numero de 0´s (el valor de n) y la otra sera la cinta en la que generaremos las cadenas del lenguage L={anb^2nc^n, para todo n mayor o igual que 0}.
La posicion inical del los cabezales en las cintas serán:
Cinta1: ...B000B...
Cinta2: ...BBB...
Por cada 0 que se lea en la cinta uno se escribirá en la cinta dos una a. El proceso se repite hasta que en la cinta uno lea un B. En este caso, se cambia la dirección de lectura en la cinta 1 hacia la izquierda cambiando de estado. Para escribir las b´s en las cinta de salida, haremos un barrido a la izquierda imprimiendo por cada 0 una b y despues otro barrido hacia la derecha repitiendo el mismo proceso de escritura dos. Finalmente, haremos un ultimo barrido para escribir el ultimos conjunto de a´s. En este caso, cuando en la cinta 1 se encuentre un B, escribiremos un 0 para la siguiente iteración, al tiempo que en la cinta dos escribimos un delimitador(#)para separar las siguiente cadena del lenguaje. Se vuelve al estado incial para volver a escribir la nueva cadena.
La salida será:
Cinta 2: ...Baaabbbbbbaaa#aaaabbbbbbbbaaaa#.......
| [0,B] | [B,B] | |
| q0 | {q0,{0,R},{a,R}} | {q1,{B,L},{B,Z}} |
| q1 | {q1,{0,L},{b,R}} | {q2,{B,R},{B,Z}} |
| q2 | {q2,{0,R},{b,R}} | {q3,{B,L},{B,Z}} |
| q3 | {q3,{0,L},{a,R}} | {q0,{0,Z},{#,R}} |
1 comentario:
La cinta A en principio empiza ya con un 0 minimo no?creo que deberiais tener en cuenta que tambien puede estar la cadena vacia y empezar poniendo dos delimitadores juntos y empeza con que la cinta A este vacia y cuando ponga esos dos delimitadores que son la cadena vacia ya vaya incrementando.Que vaya de la cadena vacia a 1 cero, luego 2, lueg 3....
de todas formas funciona bien si lo quereis modificar es facil es añadir dos estados inciales sin mas.pero va bien a partir de que tenga un 0 minimo.
Publicar un comentario