AUTOMATAS

ACTIVIDAD 14

TRABAJO COLABORATIVO 3

ANA MILENA PALACIOS

WALTER ANDRES PALOMINO BOCANEGRA

1117500576

Curso AUTÓMATAS Y LENGUAJES FORMALES

Código 301405

Tutor JAIME JOSE VALDES

Universidad Nacional Abierta y a Distancia – UNAD

Mayo de 2013

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.

Identifique una cadena que no sea válida y justifíquela porque.

No es válida la cadena “yxxy” porque empieza por “y”, y en la MT no existen transiciones que nos lleven del estado inicial con el carácter “y”.

No es válida la cadena “xxxx” ya que termina en “x” y no existen transiciones que nos lleven al estado final (halt) consumiendo una “x”.

Identifique los componentes de la Máquina de Turing (descríbala).

La MT está representada por el quíntuplo (K,Σ,Γ,δ,q0) donde:

K={q0,q1,q2}, es el conjunto de estados, tal que q2 es el estado halt.

Σ={x,y}, es el alfabeto de entrada.

Γ={⊔,x,y,z}, es el alfabeto de la cinta.

δ=(K-{q2}×Γ)→K×(Γ∪{L,R})= {{(q0,x)=(q0,R)},{(q0,x)=(q1,R)},{(q1,x)=(q1,R)},{(q1,z)=(q0,R)},{(q1,y)=(q2,z)}} es la función de transición.

q0, es el estado inicial.

Diseñe una MT que reconozca {0n1n : 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.

Identifique la función de transición.

La MT está representada por el quíntuplo (K,Σ,Γ,δ,q0) donde:

K={q0,q1,q2,q3,q4,q5}, es el conjunto de estados, tal que q5 es el estado HALT.

Σ={0,1}, es el alfabeto de entrada.

Γ={⊔,x,y,0,1}, es el alfabeto de la cinta.

δ=(K-{q5}×Γ)→K×Γ×({L,R})=

...