Trabcol3 Algoritmos

TRABAJO COLABORATIVO N°2

AUTOMATAS Y LENGUAJES FORMALES

301405_49

PRESENTADO POR:

YEIMY YURIED NIÑO HERNANDEZ

COD. 1053302104

VICTOR JAVIER CARRILLO PATERMINA

COD.1052962492

DARIO ROLANDO ROJAS LOPEZ

COD.1052387168

ANDRES CONTRERAS HERNANDEZ

COD. 1052385578

PRESENTADO A:

JAIME JOSE VALDES

UNIVERSIDAD NACIONAL ABIERTA Y ADISTANCIA

UNAD

ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERIA

PROGRAMA DE INGENIERÍA SISTEMAS

MAYO 2012

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

El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de maquinas más pequeñas, mediante diagramas de transiciones.

La construcción de máquinas 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

 Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.

 Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos 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.

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

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

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

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

Calcule la función

Grafíquela e identifique sus elementos.

Desarrollo:

Cuando se cambia un 0 por una x, entonces se mueve hacia la derecha, pasando por encima de los ceros e Y, hasta llegar al primer 1.

Cuando se cambia el 1 por la Y, se mueve hacia la izquierda por encima de todos los Y y de todos los ceros hasta llegar a una X y se repite el proceso hasta que sólo queden Xs y Ys.

El MT quedo en un estado de aceptación y la cadena es reconocido.

...