Maquina de Turing; ejercicios

2108 palabras 9 páginas
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

Documentos relacionados

  • Maquina Turing Suma Binarios
    2427 palabras | 10 páginas
  • La maquina de turing
    2508 palabras | 11 páginas
  • Ensayo: tesis de church-turing y la no computabilidad
    873 palabras | 4 páginas
  • Maquina de vapor
    2456 palabras | 10 páginas
  • Variantes de la maquina de turing
    1452 palabras | 6 páginas
  • Manejo de maquinas
    6455 palabras | 26 páginas
  • Ejercicios hombre - maquina
    2100 palabras | 9 páginas
  • Ejercicios de paa cn respuesta
    2593 palabras | 11 páginas
  • Turing
    1330 palabras | 6 páginas
  • Manejo de maquinas
    6466 palabras | 26 páginas