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

...