EJERCICIOS

Unidad 3

AUTÓMATAS DETERMINISTAS (AFD) 

AUTÓMATAS NO DETERMINISTAS (AFND) 

MAQUINA DE TURING (EJERCICIOS)

1. Diseñar una Máquina de Turing que calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0's por 1's y los 1's por 0's). Solución: Algoritmo: Recorrer la cinta de izquierda a derecha, sustituyendo 1's por 0's y viceversa. Definición de la MT Necesitamos implementar una Máquina de Turing que se comporte como transductor, porque genera una salida en la cinta. Tendremos un solo estado, que será el inicial, q0, sobre el que se realizan todas las transiciones MT1=({0,1},{0,1,},,{q0},q0,f,{Φ}), donde f: 

Si además se exige que el transductor termine en un estado final y pare, si la entrada es correcta, es decir, una simple secuencia de ceros y unos, la solución sería: MT1.2=({0,1},{0,1,},,{q0,q1},q0,f,{q1}), donde f: 

Si además del estado final se exige que la cabeza de la pila termine al inicio de la palabra, se obtiene la siguiente máquina de Turing: MT1.3=({0,1},{0,1,},,{q0,q1,q2},q0,f,{q2}), donde f: 

2. Diseñar una Máquina de Turing que obtenga el sucesor de un número en codificación unaria. Considerar en la codificación unaria que el 0 se representa por la cadena vacía, el 1 por 1, el 2 por 11, etc. Solución: La representación de un número en unario, según las indicaciones del enunciado es: 

n => n+1 "unos" (decimal) (unario) 

Así: 0 => cadena vacía

1 => 1 

2 => 11 

3 => 111

 4 => 1111 

5 => 11111

Algoritmo: Sucesor unario: Recorrir número hasta el final [transición recursiva en q0], y allí añadir un 1 adicional, a la derecha de la secuencia de 1's [transición de q0 a q1].

Definición de la MT MT2=({1},{1,},,{q0,q1},q0,f,{q1}), donde f: 

3. Diseñar una Máquina de Turing que obtenga el predecesor de un número en codificación unaria. Considerar la codificación unaria del 0 igual que en el ejercicio 2.

Solución:

Algoritmo: Predecesor unario: Recorrer número hasta el final [transición recursiva en q0], situarse en el último dígito [transición q0 a q1, moviendo puntero a la izquierda], y escribir un blanco encima para borrarlo [transición q1 a q2].

Definición de la MT MT3.1=({1},{1,},,{q0,q1,q2},q0,f,{q2}), donde f: 

Si además se quiere que la cabeza lectora de la máquina de Turing apunte al primer símbolo de la palabra, se necesita una transición recursiva en q2, para recorrer la cinta hacia la izquierda, y un nuevo estado final, q3, al que transitar al llegar al símbolo de celda vacía, quedando la siguiente

MT: MT3.2=({1},{1,},,{q0,q1,q2,q3},q0,f,{q3}), donde f:

4. Diseñar una Máquina de Turing que calcule la paridad de un número binario. Es decir, si el número de 1's de la cadena es par, se añade un 0 al final, y si es impar, se añade un 1. 

Solución: 

Algoritmo: Recorrer de izquierda a derecha, recordando si se lleva un nº de 1's par o impar (situándose en un estado diferente), para añadir al final 0 ó 1, respectivamente. 

Definición de la MT 

MT4=({0,1},{0,1,},,{PAR, IMPAR, qf},PAR,f,{qf}), donde f: 

Definición de estados: 

El estado "PAR", representa que se ha leído un número de 1's par (considerando el 0 par). El estado "IMPAR", representa que se ha leído un número de 1's impar. El estado "qf" es el estado final, al que se llega sólo al final, tras añadir el 1 ó 0 de paridad de 1's. 

Definición de transiciones: 

Mientras se recorre la cadena, la máquina de Turing transita entre los estados PAR o IMPAR, dependiendo de la cantidad de 1's de la subcadena leída hasta el momento. En cualquiera de los dos estados: 

- si se lee un 1, se cambia de estado, porque ha cambiado la paridad del número.

- si se lee un 0, se mantiene en el mismo estado, porque no ha cambiado la paridad.

- si se lee un blanco, se transita al estado final y se para, tras escribir un dígito distinto según el estado actual de la máquina: 

o PAR (nº de 1's par): escribir un 0, para mantener la paridad existente.

o IMPAR (nº de 1's impar): escribir un 1, para conseguir un número de 1's par. 

EJEMPLOS DEL LINK