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 en enunciados 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 …ver más…

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

Teoría de Autómatas y Lenguajes Formales.

Ejercicios de Máquinas de Turing

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.
Solución:
Dado que no se especifica si se debe mantener la cadena original de a’s, b’s y c’s, se pueden asumir