TALF-SANCHIS-LEDE

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Máquinas de Turing


 
Teoría
 de
 Autómatas
 y
 
Lenguajes
 Formales
 
Ejercicios
 de
 
Máquinas
 de
 Turing
 

Autores:
Araceli Sanchis de Miguel
Agapito Ledezma Espino
Jose A. Iglesias Martínez
Beatriz García Jiménez
Juan Manuel Alonso Weber

* Algunos ejercicios están basados enenunciados de los siguientes libros:
• Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón
Salomón. Teoría de autómatas y lenguajes formales. McGraw-Hill (2007).
• Manuel Alfonseca, Justo Sancho, Miguel Martínez Orga. Teoría de lenguajes,
gramáticas y autómatas. Publicaciones R.A.E.C. (1997).
• Pedro Isasi, Paloma Martínez y Daniel Borrajo. Lenguajes, Gramáticas y
Autómatas. Unenfoque práctico. Addison-Wesley (1997).

1

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Máquinas de Turing

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).
2. Diseñar una Máquina de Turing que obtenga el sucesor de un número en codificación
unaria. Considerar en la codificaciónunaria que el 0 se representa por la cadena vacía,
el 1 por 1, el 2 por 11, etc.
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.
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 alfinal, y si es impar, se añade un
1.
5. Diseñar una Máquina de Turing que sea un contador unario de caracteres del lenguaje
con alfabeto Σ = {a,b,c}. Es decir, se deben devolver tantos 1’s como caracteres haya en
la palabra de entrada. Considerar la codificación unaria del 0 igual que en el ejercicio 2.
6. Diseñar una Máquina de Turing que haga una copia de una cadena de símbolos
{A,B,C}. Porejemplo, para la entrada “bAABCAb” devuelve en la cinta
“bAABCAAABCAb”, donde ‘b’ representa el blanco.
7. Diseñar una Máquina de Turing que tome como entrada una cadena con M 1’s y N A’s
(M
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], yallí 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:

5

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Máquinas de Turing

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 elejercicio 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 deTuring 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:

6

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Máquinas de Turing

q3

7Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Máquinas de Turing

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...