Trabajo 3 Automatas

INTRODUCCION

Con los conocimientos adquiridos en la realización del primer y segundo trabajo colaborativo, logramos un gran acoplamiento para trabajar con autónomas y lenguajes formales, en este trabajo se complementará ese conocimiento con lo aprendido en la unidad 3 del curso, en donde trabajemos con las Maquinas de Turing y sus funciones recursivas. Crearemos y diseñadores diferentes puntos a medida que se necesite acoplar una maquina

Haremos uso de los compiladores de los mismos trabajos colaborativos pasados para ilustrar y evidenciar la realización de los puntos de la actividad.

OBJETIVO GENERAL

Reconocer y evaluar 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.

OBJETIVOS ESPECÍFICOS:

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

• Recrear y proponer nuevos metidos y diseños de maquinas.

• Optimizar y explicar las maquinas realizadas para un mejor entendimiento.

DESARROLLO DE LA ACTIVIDAD

Dado el alfabeto Σ={x,y} de la siguiente maquina de Turing, determine:

Lenguaje que acepta

El lenguaje que acepta la máquina es el conjunto de palabras que la llevan desde el estado inicial al estado final (halt). Está dado por:

{x^n y∶n≥1}

Recorra la máquina con al menos una cadena válida.

Dada la MT recreada con JFLAP:

El recorrido para la cadena “xxxy” en el simulador es:

Se lee la primer “x” y se avanza a la derecha. Se cambia al estado q1.

Se lee el segundo carácter “x”, se avanza a la derecha el cabezal y se continúa en el estado q1.

Se lee el tercer carácter “x”, se continúa en el estado q1.

Finalmente se lee el último carácter “y”, se escribe el carácter “z” en la cinta, el cabezal permanece en el mismo sitio y se cambia al estado q2 que es final (estado halt). Se acepta la palabra.

...