Trabajo Col 3

INTRODUCCION



considerar las máquinas abstractas que permiten solucionar ciertos tipos de algoritmos, los algoritmos en los que no puede recordarse más que una cantidad fija de información y otros en los que la información desarrollada durante la ejecución del algoritmo puede recuperarse solo en concordancia con la regla “lifo” últimos en entrar primeros en salir, enesta unidad se describe una maquina abstracta, llamada Máquina de Turing , que es aceptada de manera amplia como modelo general de computación, aunque las operaciones básicas de esta máquina son comparables en su sencillez a las de las máquinas estudiadas en las unidades anteriores, las nuevas maquinas pueden realizar una amplia variedad de operaciones de cómputo.

Además de aceptarlenguajes les es posible computar funciones y de conformidad con la tesis de Church-Turing, ejecutar casi cualquier procedimiento algorítmico concebible.



OBJETIVO GENERAL

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.

OBJETIVOS ESPECÍFICOS:

Estudiar las Máquinasde Turing y sus propiedades básicas

EJERCICIOS A DESARROLLAR:



1. Dado el alfabeto Σ={x,y} de la siguiente Máquina de Turing, determine:





• El lenguaje que acepta
• Recorra la máquina con al menos una cadena válida.
• Identifique una cadena que no sea válida y justifíquela porque.
• Identifique los componentes de la Máquina de Turing (descríbala).

2. Diseñe una MT quereconozca {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.



3. Construya una MT que acepte el Lenguaje (represéntela

L = {aibici: 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.

• 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.

• Identifique en qué momento la máquina de Turingse detiene.
• Calcule la función δ
• Grafíquela e identifique sus elementos.

4. Construir una MT que reconozca L = 01*+ = 10*

Para la Máquina M = (Q, Σ, ┌ , q0, T , B , δ)
Q = { q0, q1} x {0,1,B} Estado inicial [q0, B]
Estado final [q 1, B]
La función de transición δ está dada por:

δ ([q0, B] , 0 ) = ([q1, 0], 0 , D) δ ([q0, 0] , 1 ) = ([q1, 0], 1 , D) δ ([q0, 0] , B ) = ([q1, B], B, D) δ ([q0, B] , 1 ) = ([q1, 1], 1 , D) δ ([q1, 1] , 0 ) = ([q1, 1], 0 , D) δ ([q1, 1] , B ) = ([q1, B], B , D)


• Identifique una cadena válida.

5. Para la siguiente Máquina de Turing (MT):



























• Identifique que pasa cuando inicia con la cadena yyxyxx (demuéstrelo con el
recorrido de la misma)

• Plásmela en el simulador (debeentregar el archivo generado por el simulador), Las imágenes capturadas van inmersas en el desarrollo del trabajo.

• Con base en esa MT, proponga una nueva máquina que se comporte diferente cuando inicia con la cadena yyxyxx


6. Considere la máquina de Turing de la figura con el alfabeto {x,y,z} e indique que tipo de cadenas decide el lenguaje que acepta.



• Dentro del RunTest y elrecorrido de la cinta, Ubique en su cinta la secuencia
xy y que sea sustituida por zz. Identifique cuando se detiene la máquina cuando hace esta operación
• Plásmela en el simulador. Las imágenes capturadas van inmersas en el desarrollo del trabajo.
• Ejecute el RunTest a la cadena aceptada (muéstrela en la captura de imagen para el trabajo




DESARROLLO


2. Diseñe una MT que reconozca...