Automatas

CONSTRUCCION MODULAR DE UNA MAQUINA TURING

Ejemplo: 25.3E-18

Definición: Forma sentencia

Sea G = una gramática

a) S es una forma sentencial

b) Si S es una forma sentencial y P, entonces N es también una forma sentencial.

Una forma sentencial que no contiene no-terminales se llama sentencia generada por G.

Definición: El lenguaje generado por una gramática G, denotado por L (G), es el conjunto de sentencias generadas por G.

Definición: Sea G=

+cierre transitivo

2. Diseñe una MT que reconozca {0n1n : n ≥ 1 }

•Cambie un 0 por una x (explique qué pasa con la máquina).

Se mueve hacia la derecha, pasando por encima de los ceros e Y , hasta llegar al primer 1.

•Cambie un 1 por una y (explique qué pasa con la máquina).

Se mueve hacia la izquierda por encima de todos los Y y de todos los ceros hasta llegar a una X y se repite el proceso hasta que solo queden Xs y Ys.

•Identifique en qué momento la máquina de Turing se detiene.

Se detiene en el estado de aceptación q4 después de hacer paso por el símbolo “B” en blanco, tal y como lo podemos ver en la siguiente imagen:

•Calcule la función 

La función se define así:

(q0, 0) = (q1,X,D)

 (q1, 0) = (q1, 0,D)

 (q1,X) = (q1,X,D)

 (q1, 1) = (q2, Y, I)

 (q2, Y ) = (q2, Y, I)

 (q2, 0) = (q2, 0, I)

 (q2,X) = (q0,X,D)

 (q0, Y ) = (q3, Y,D)

 (q3, Y ) = (q3, Y,D)

 (q3,B) = (q4,B,D)

Sea T = {q4}

Sea w = 1100

q00011 Xq111 X0q111 Xq20Y 1

1. q2X0Y 1 Xq00Y 1 XXq1Y 1

1. XXY q11 XXq2Y Y Xq2XY Y

1. XXq0Y Y XXY q3Y

1. XXY Y q3B XXY Y Bq4B

La Máquina de Turing se detiene porque quedó en un estado de aceptación y la cadena es reconocida.

• Grafíquela e identifique sus elementos.

7. Haciendo uso de un simulador, y con ayuda de su tutor (asesoría), monte uno (de los cuatro ejercicios anteriores 3, 4 5 ó 6) en un simulador y recorra la máquina, verificando sus estados iniciales, finales, parada, inicio, etc.

Tenga en cuenta que la construcción de las máquinas (los diagramas de Moore) solo son permitidos si son generados por un simulador.

Inicio en  (q0, a) = (q0, a,D)

Enseguida se halla con una parada en  (q0, a) = (q0, a,D)

Después sigue en  (q1, a) = (q1, a,D)

Siguiente paso  (q1,B) = (q2,B, I)

Y Por último creamos el estado final

...