Taller de Máquina de Turing

Solución de problemas con MT, aplicaciones de autómatas y  máquinas de estado 

Ricardo Alberto Quintero

Julio Cesar Castaño

Facultad de Ingeniería Institución Universitaria Digital de Antioquia

Autómatas, Gramáticas y Lenguajes

Medellín 

Taller de Máquina de Turing

[pic 1]

[pic 2]

[pic 3]

Pruebas:

[pic 4]

Tabla de transición:

Séptupla:

[pic 8]

Prueba paso a paso:  

[pic 9]

1. Una cadena compuesta con 0 y 1, debe convertir cada 0 en 1 y cada 1 en 0

[pic 10]

Prueba:

[pic 11]

Tabla de transición:

Séptupla:

[pic 15]

Prueba paso a paso:  

[pic 16]

1. Una cadena compuesta con 0 y 1, debe contar el número de 1 que se encuentren en la cadena. Por ejemplo, en una cadena 011010, el resultado debe contener sin importar lo que esté a la izquierda, uno o varios espacios vacíos 111 espacios vacíos (puede ser 111, aaa, XXX, lo importante es que indique el número de unos)

[pic 17]

Pruebas

[pic 18]

Tabla de transición

Séptupla:

[pic 27]

Prueba paso a paso:  

[pic 28]

1. Cree un enunciado propio que pueda ser una aplicación de la máquina de Turing

Crear una maquina de Turing que duplique la entrada, por ejemplo 𝑎𝑎 en 𝑎𝑎𝑎𝑎 o 𝑎𝑎𝑎 en

𝑎𝑎𝑎𝑎𝑎𝑎

[pic 29]

Pruebas:

[pic 30]

Tabla de transición:

...