Trabajo Colaborativo

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 porla 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áquinanopodí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 aceptaRecorra 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 validaporque 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 lamá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 detransiciones 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 deaceptació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)...