automatas

1. Identifique los componentes de la Máquina de Turing (descríbala).
2. Diseñe en un Diagrama de Moore una máquina de Turing, que sea de autoría propia (No puede ser copia de internet) donde ustedes creen las condiciones.
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.
4. Identifique una cadena que no sea válida yjustifíquela porque.
5. Ejecute el RunTest a una cadena aceptada que tenga al menos cinco símbolos
6. Identifique en que momento la máquina se detiene.
7. Mencione cual es la diferencia entre una MT que actúa como transductor y una que actúa como reconocedor


1. Máquina de Turing.
Una máquina de Turing es una séptupla
M= (Γ,Σ,•,Q,q0,f,F) donde:

1.Γ es el alfabeto de símbolos de la cinta
2.Σ⊂ Γ es el alfabeto de símbolos de entrada
3.• ∈ Γes el símbolo blanco que no pertenece a Σ
4. Q es un conjunto finito de estados
5. q0 ∈ Q es el estado inicial
6. F ⊆ Q es el conjunto de estados finales
7.f es una función de transición parcial
f: Q × Γ→Q×Γ×{L,R}


2. PRIMER EJERCICIO
Esta máquina de Turing compara la paridad de letras a y b, es decir, reconoce el lenguaje L={a n b n} e intercambialas letras a por las letras b.

Componentes Máquina de turing.
M= ({a,b,x,y},{a,b},,{q0,q1,q2,q3,q4,q5},q0,f,q5)

3. RECORRIDO CON UNA CADENA VÁLIDA
Cadena: aabb

Inicialmente se encuentra en el estado q0, cuando lee la letra ‘a’ escribe ‘x’ y se mueve a la derecha y cambia al estado q1.



En el estado q1 lee la letra ‘a’, escribe ‘a’, se mueve a la derecha y permanece en el estado.


Lee laletra ‘b’, escribe ‘y’, se mueve a la izquierda y cambia al estado q2.

En q2 lee la letra ‘a’, escribe ‘a’, se mueve a la izquierda y permanece en el mismo estado.

De nuevo en el estado q2, lee la letra ‘x’, escribe ‘x’, se mueve a la derecha y cambia al estado q0.

En q0 lee la letra ‘a’ y realiza el mismo procedimiento anteriormente descrito.

En q1 lee la letra ‘y’, escribe ‘y’, se mueve a laderecha y permanece en el mismo estado.


De nuevo en q1 lee la letra ‘b’ y realiza el procedimiento antes descrito.

En q2, lee la letra ‘y’, escribe ‘y’, se mueve a la izquierda y permanece en el mismo estado.


Continuando en q2, lee la letra x, escribe ‘x’, se mueve a la derecha y cambia al estado q0.


En q0, lee ‘y’, escribe ‘y’, se mueve a la derecha y cambia al estado q3.


En q3, lee ‘y’,escribe ‘y’, se mueve a la derecha y permanece en q3


En q3, le al final la cadena vacía, escribe la cadena vacía, se mueve a la izquierda y cambia al estado q4.


En q4 cuando lee ‘x’, escribe ‘b’, se mueve a la izquierda y permanece en el mismo estado y a su veces cuando lee ‘y’, escribe ‘a’, se mueve a la izquierda y permanece en el mismo estado.









En q4, le la cadena vacía, escribe lacadena vacía, se mueve a la derecha y cambia al estado q5 y acepta.



4.CADENA NO VÁLIDA

Una cadena no valida seria cualquier combinación de letras ‘a’ y ‘b’ en el cual el número de ‘a’s y ‘b’s no sea igual, Por ejemplo: aab, la maquina rechaza esta cadena ya que al inicio al leer una letra ‘a’ escribe en la cadena la letra ‘x’, luego de esto cada vez que lee la la letra ‘a’ vuelve a escribiresta misma, luego por cada letra ‘b’ que lee, escribe una ‘y’ y cambia una letra ‘a’ por ‘x’, por lo cual realizando este proceso si el número de letras ‘a’ y ‘b’ no es igual va a rechazar la cadena ya que si el número de ‘b’ es menor al número de ‘a’ no va a sustituir todas las letras ‘a’ por ‘x’ y si el número de ‘b’ es mayor llega a leer la letra ‘x’ que es la letra que esta al inicio debido alprimer intercambio de una ‘a’ por esta y al no tener más letras ‘a’ rechaza la cadena.

5. RUN TEST DE MULTIPLES CADENAS VÁLIDAS


6.RUN TEST DE MULTIPLES CADENAS NO VÁLIDAS


7- DIFERNCIA ENTRE MT QUE ACTUA COMO TRANSDUCTOR Y RECONOCEDOR
La diferencia es que las máquinas de turing que actúan como transductor esperan realizar una operación de acuerdo a una cadena de entrada, por ejemplo, que...