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

...