TRABAJO COLABORATIVO # 3 AUTOMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO # 3

AUTOMATAS Y LENGUAJES FORMALES

ESTUDIANTE:

JUAN CAMILO CORREA

C.C: 1058818590

TUTORA:

ANGELA MARÍA GONZALES

UNIVERSIDAD NACIONAL ABIERTA Y DISTANCIA

UNAD CEAD MEDELLIN

JUNIO 2015

DESARROLLO ACTIVIDAD

[pic 2][pic 3]3 EJERCICIO: DISEÑO DE UNA MT QUE ACEPTE CADENAS CON LA CINTA VACIA

La máquinas de Turing pueden reconocer cadenas llegando a un estado de aceptación o de parada “halt” aun cuando la cinta no se haya desocupado o aún tenga caracteres. Dependiendo los fines con que se construya la máquina y el tipo de información a tratar, los diseños de MT reconocedoras de lenguajes con cinta vacía al final de cada cadena aceptada pueden ser de gran utilidad y poderío computacional.

Actividades a desarrollar:

Diseñe Una MT que reconozca el lenguaje L = {0}* (incluye la cadena λ). Y que al final del recorrido de la cadena aceptada, la cinta quede vacía solo con los caracteres “blanco”. El alfabeto de la cinta debe ser diferente al alfabeto de entrada

1. Identifique los componentes de la Máquina de Turing (descríbala).

La Máquina de Turing es un modelo matemático que se puede definir como un

Séptuplo (𝐾, Σ, 𝑠, 𝐵, 𝑇, Γ, 𝛿, ) en donde:

𝐊= es un conjunto de estados tal forma que h ∈ K donde h es el estado de

aceptación y pertenece al conjunto de estados K. K={𝑞4, 𝑞5, 𝑞6}

Σ = es el alfabeto de entrada (palabras de entrada) donde Ц ∉ Σ. Σ ={0, 𝐾}

(Símbolo blanco Ц pertenece al alfabeto de la cinta no al alfabeto de las

palabras que se van a reconocer)

s ∈ K es el estado inicial que pertenece al conjunto de estados K. s={𝑞4}

T ⊆ K es el estado final que pertenece al conjunto de estados K. T = {𝑞6}

B ⊆ 𝚪 es el símbolo carácter blanco que está inmerso en el alfabeto de la cinta

𝚪.

𝚪 = es el alfabeto de la cinta, donde Ц ∈ Γ y Σ ⊆ Γ. Γ ={𝐾}

(Símbolo blanco pertenece al conjunto de símbolos del alfabeto de la cinta de y

el alfabeto de la cinta contiene al alfabeto de entrada)

𝜹: Es la función de transición (𝐊 − {𝐡} 𝐱 𝚪) → 𝐊 𝐱 (𝚪 ∪ {𝐋, 𝐑})

(q4, 0) = (q4, K, D)

(q4, B) = (q5, B, I)

(q5, K) = (q5, B, I)

(q5, B) = (q6, B, D)

2. Diséñela en un Diagrama de Moore.

[pic 4]

3. Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada.

Cadena válida: 000

[pic 5]

La máquina inicia en el estado q4, con la cabeza lectora ubicada en el primer 0 de la izquierda.

...