trabajo cola bora tivo 3
TRANSCRIPT
TRABAJO COLABORATIVO 3
TUTOR: ING. JAIME JOSE VALDES
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD INGENIERIA DE SISTEMAS
AUTOMATAS Y LENGUAJES FORMALES
INTRODUCCIÓN
La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “Oncomputable numbers, with an application to the Entscheidungs problema”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquinano podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo. Una máquina de Turing con una sola cinta puede ser definida como
una 6-tupla, donde Qes un conjunto finito de estados es un conjunto finito de
símbolos de cinta, el alfabeto de cinta
1. Dado el alfabeto ∑={x,y} de la siguiente Máquina de Tutring, 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).
DESARROLLO
Lenguaje que acepta :
Ø Ø Ø
Ø ¬a
Xxa
¬xz¬xxa
Recorra la máquina con al menos una cadena válida.
Identifique una cadena que no sea válida y justifíquela porque.
Cadena RRRR No es valida porque el autómata reconoce solo en lenguaje {x,y, Ø } Ø Ø ¬ No es valido porque no sigue la secuencia de la cinta del autómata
Identifique los componentes de la Máquina de Turing (descríbala).
2 . Diseñe una MT que reconozca { : 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 función se define así:
(q0, 0) = (q1, X, R)
(q1, 0) = (q1, 0, R)
(q1, X) = (q1, X, R)
(q1, 1) = (q2, Y, L)
(q2, Y) = (q2, Y, L)
(q2, 0) = (q2, 0, L)
(q2, X) = (q0, X, R)
(q0, Y) = (q3, Y, R)
(q3, Y) = (q3, Y, R)
(q3, B) = (q4, B, R)
Sea T = {q4} sea w = 1100 q00011 - Xq111 - X0q111 - Xq20Y 1
-q2X0Y 1 - Xq00Y 1 - XXq1Y 1 -XXY q11 - XXq2Y Y - Xq2XY Y - XXq0Y Y - XXY q3Y -XXY Y q3B - XXY Y Bq4B
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 Turing se detiene.
Calcule la función
1. Se cambia la a por una X y se mueve hacia la derecha pasando por
encima de todas las a0s e Y s, hasta llegar a la primera b, cambia la
primera b por una Y, se mueve a la derecha pasando por encima de las
bs y Zs y luego encuentra la primera c y la cambia por Z y se mueve a la
izquierda.
Luego se mueva a la izquierda pasando por encima de bs, Y s, as, hasta
encontrar la X la reemplaza por una X y repite el proceso anterior, cuando la
maquina reemplaza la cadena X, Y y Zs reconoce la cadena vacía y busca el
estado de aceptación.
4. Construir una MT que reconozca L= 01* + 10*
Para la Máquina M = (Q, ∑, ┌ , q0 , T , B ,
Q = {q0, q1} × {0, 1, B} Estado inicial [q0, B] Estado final [q1, B]
La función de transición esta dad por:
([q0, B], 0) = ([q1, 0], 0,)
([q1, 0], 1) = ([q1, 0], 1, D)
([q1, 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)
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 (debe entregar el archivo generado por el
simulador), Las imágenes capturadas van inmersas en el desarrollo del trabajo
• Con base en esa MT, preponga una nueva máquina que se comporte
diferente cuando inicia con la cadena yyxyxx
Con la cadena yyxyxx el autómata llega hasta el estado q0 o inicial
.Con base en esa MT, preponga 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 el recorrido 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).
En esta imagen se puede observar que la MT se detiene en q3 y no llega a su
final puesto que se le dio la cadena de caracteres xy Ø(vacío), pues que los
primeros caracteres se van por la cadena R y el Ø(vacío) se tiende a ir por la
cadena L esto hace que no continúe la Maquina de Turing.
CONCLUSION
La máquina de Turíng es una máquina mediante la cual es posible la
categorización de problemas computacionales mediante el análisis de
complejidad de algoritmos, de acuerdo a su comportamiento.
BIBLIOGRAFIA:
De Wikipedia, la enciclopedia libreSaltar a navegación, búsqueda Feynman,
Richard (1996).
Conferencias sobre computación, graficromo. ISBN 84-8432-444-3. Consultado
el 11 de Julio del 2010.
Viso, Elisa (2008). Introducción a la teoría de la computación. ISBN 978-970-
32-5415-6.Consultado el 11 de Julio del 2010.
De Castro, Rodrigo (2004). Teoria de la computacion : lenguajes, automatas,
gramáticas .Consultado el 15 de Julio del 2010.
«on computable numbers,with an application to the entscheidungsproblem» (en
español).Consultado el 15 de Julio de 2010.
«Variantes de una Máquina de Turing» (en español). Consultado el 11 de Julio
de 2010.
Obtenido de
"http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing"Categorías: Máquinas
de Turing | Gramática generativa