Automatas Y Lenguajes Formales

AUTÓMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO No. 3

Estudiantes:

ÁNGEL MARÍA BELLO PÉREZ

Código: 301405

angelmbello@yahoo.com

MAURICIO EFRAIN PATIÑO

Código: 13072206

maupa2007@hotmail.com

CEAD: PASTO

JUAN CARLOS RUIZ ROJAS

Código: 12911821

juancarlosruizrojas@gmail.com

CEAD: PASTO

GRUPO: 11

Tutor:

ING. CARLOS ALBERTO AMAYA TARAZONA

carlos.amaya@unad.edu.co

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD

ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA

PROGRAMA INGENIERÍA DE SISTEMAS

MAYO 2012

INTRODUCCIÓN

Se pretende mediante este trabajo describir el poder computacional de las maquinas de turing, sus operaciones básicas y la solución de problemas computacionales.

Empezaremos por definir algunos de los conceptos claves para el proceso de aprendizaje:

Las máquinas de Turing son máquinas formales, es decir sin cables ni componentes físicos. Su finalidad es definir los cálculos a partir de las operaciones más sencillas posibles, y utilizando las cuales calcular efectivamente funciones dadas. Las funciones que así pueden realizarse se llaman funciones calculables o computables.

Este tipo de máquina consta hipotéticamente de una unidad de control capaz de interpretar las instrucciones que reciba, y de una cabeza lectora que permite leer el contenido de una de las casillas en que está dividida una memoria lineal, ilimitada en ambas direcciones de sus extremos.

OBJETIVOS:

• Reconocer la importancia y el poder computacional de las Máquinas de Turing en el contexto de la solución de problemas computacionales de reconocimiento de Lenguajes.

• Estudiar las sus propiedades básicas de las Máquinas de Turing

DESARROLLO DEL TALLER

1. Mediante un grafo explique la construcción modular de las Máquinas de Turing y describa cada uno de sus elementos.

Mediante esta técnica pueden desarrollarse maquinas de Turing complejas a partir de bloques de elementales a partir de maquinas más pequeñas mediaste diagramas de transiciones.

La construcción de maquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.

Pasos para la construcción de una máquina de Turing

• Se eliminan las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.

• Se eliminan las características de detención de los estados de parada de todas la maquinas y se introduce un nuevo estado de parada que no se encuentre en ninguno de los diagramas que se combinan.

• Para cada uno de los antiguos estados de parada p y cada x en y.

Los diagramas compuestos para la construcción modular de una máquina de Turing son aquellos en los que cada uno de los bloques de construcción se representa como un nodo, con flechas entre dichos nodos para indicar las transiciones entre bloques.

Se puede combinar dos máquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. El contenido de la cinta cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de lectura/escritura de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

Máquina de Turing Compuesta.

2. Diseñe una MT que reconozca {0n1n: n ≥ 1}

Cambie un 0 por una Y (explique qué pasa con la máquina).

Cuando se cambia un 0 por una X la cabeza se cambia de posición rumbo a la derecha hasta llegar y encontrar el primer 1 lo que hace que la maquina se mueva a la izquierda de la cinta.

Cambie un 1 por una Y (explique qué pasa con la máquina).

Cuando se cambia un 1 por una Y la cabeza se cambia de posición rumbo a la derecha hasta que llega y encuentra el primer cero, lo que hace que la maquina avance a la derecha de la cinta.

Identifique en qué momento la máquina de Turing se detiene.

La máquina de Turing se detiene cuando la maquina cambió y pasó por encima de todos las entradas Y, y ya todos los 1 se hayan cambiado y solo quedan Y’s y X’s en la cinta.

Calcule la función

Grafíquela e identifique sus elementos.

3. Construya una MT que acepte el Lenguaje ( represente la

L = { ai,bi,ci: i ≥ 0} sobre Σ = {a,b,c}

• Se cambia la a por una x moviéndose a la derecha. ( explique qué pasa con la máquina) . Represente los movimientos en la tabla de transiciones para MT.

Pasa por encima de todas las a0s e Y s, hasta llegar a la primera b, cambia la primera b por una Y, se mueve a la derecha pasando por encima de las bs y Zs y luego encuentra la primera c y la cambia por Z y se mueve a la izquierda.

• Luego se mueve a la izquierda pasando por encima de las bs (bes) (explique qué pasa con la máquina). Represente los movimientos en la tabla de transiciones para MT.

Se encuentra con las Ys, as, hasta encontrar la X la reemplaza por una X y repite el proceso anterior.

• Identifique en qué momento la máquina de Turing se detiene.

La máquina se detiene después de haber realizado el proceso antes descrito hasta llegar al estado de aceptación q5 y haber reconocido al final la cadena vacía.

• Calcule la función δ

• Grafíquela e identifique sus elementos.

4. En el siguiente diseño de máquina de Turing (MT), identifique cuales

operaciones realiza y que son válidas acordes a la forma de “operar” o

“trabajar” una MT. : Sea ordenado en la descripción acorde a los pasos,

posiciones y operaciones que hace la MT.

R/ Se podría decir (especular) que la MT tiene tres estados:

• Primero que acepta entradas para {a, b} y permanece en eseestado hasta que la cabeza lea un carácter ($), entonces, la cinta avanzará

...