DESARROLLO MOMENTO 3

VLADIMIR RODRIGUEZ

JOSE EDINSON ROJAS CALDON

CODIGO 1081413279

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD

CURSO DE AUTOMATAS Y LENGUAJES FORMALES

2016

EJERCICIO 1Diseñe Una MT que se comporte como reconocedor que reconozca el lenguaje L ={an bn; n >= 1} (NO incluye o NO acepta la cadena λ). El alfabeto de la cinta debe ser diferente al alfabeto de entrada. Es decir el alfabeto de entrada es “a” y el de la cinta “1” con sus respectivos símbolos blancos si es que los necesita en su diseño.

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

Una cinta de longitud infinita. Un cabezal o control finito   Un registro de estado  Una tabla de acción o función de transición

La presente MT se define como un 7-tupla { Q, q0, Σ, qF, δ, Γ } consistente de los siguientes componentes:

Un conjunto finito de estados ( Q ) Un estado inicial ( q0 ) el cual es un elemento de (Q ) Un conjunto finito llamado alfabeto entrada ( Σ ) compuesto por {a,b} Un conjunto de estados finales (qF ) Una función de transición de la máquina (δ : Q × Γ { , }). La flecha

denota el desplazamiento a izquierda y derecha. La transición δ ( q0, a) = ( xxx Significa: Estando en el estado q0, escaneando el símbolo a, el cabezal o unidad de control finito borra a, escribe 1 y se mueve en el estado p a la derecha. Lo mismo sucede con la b.

El alfabeto de la cinta Γ que contiene ∑ es decir ∑ Γ y contiene además {0,1}⊆ El símbolo blanco “B” o ⊔ que no hace parte del alfabeto de entrada ⊔ ∈ Γ

Punto 2: Diséñela en un Diagrama de Moore

Punto 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.

Damos ingreso por el estado inicial q0 con el alfabeto de entrada “aabb”.

La secuencia indica que al ingresar “aabb” se mantiene en el estado q0, En la cinta se reemplaza la a por 1 y da un paso a la derecha, luego reemplaza la b por 2 y da un paso a la derecha.

Al realizar el cambio de paridad, pasa al estado q1. En la cinta el 2 se mantiene en 2 y da un paso a la izquierda, si encuentra un 1 se mantiene en 1 y da un paso a la izquierda hasta llegar a un nuevo espacio en blanco.

Al llegar al espacio en blanco cambia al estado q2 o estado final. En la cinta el espacio se mantiene en espacio y finaliza la sesión.

Punto 4: Identifique una cadena que no sea válida y justifíquela porque.

Damos ingreso por el estado inicial q0 con el alfabeto de entrada “aaaabbbb2aabb”.

La secuencia indica que al ingresar “aaaabbbb” se mantiene en el estado q0, En la cinta se reemplaza la a por 1 y da un paso a la derecha, luego reemplaza la b por 2 y da un paso a la derecha, cuando llega a la entrada “2” se presenta el error, la MT quedó en un estado de NO aceptación y la cadena no es reconocida, por lo tanto no continúa el recorrido.

Punto 5: Ejecute el RunTest a una cadena aceptada que tenga al menos cinco símbolos

Punto 6: Identifique en que momento la máquina se de tiene.

La máquina se detiene al momento de evaluar un carácter blanco o vacío, y al final y cuando la cadena llega a su estado de aceptación.

Punto 7: Lo que acaba de diseñar es una MUT o una MT. Justifique su respuesta.

El diseño corresponde a un MT (realizar cualquier cálculo específico -MT particular- sobre cualquier configuración inicial de entrada correcta para esa MT particular). Por el contrario una máquina Universal de Turing MUT está diseñada para realizar un cálculo específico y no para procesar cualquier información.

Punto 8: Mencione y justifique las semejanzas y diferencias entre una Máquina de Turing reconocedora y una Maquina de Turing Transductora

MT que actúa como TRANSDUCTOR: Modifica el contenido de la cinta realizando cierta función.

Ejs: MT que sustituye los dígitos por cero,MT que añade un bit de paridad a la entrada,

MT que duplica el número de 1s que hay en la cinta Si la Entrada está bien formada: debe terminar en un Estado

Final. Si la Entrada No está bien formada: debe terminar en un

estado No Final. MT que actúa como RECONOCEDOR:

MT capaz de RECONOCER o ACEPTAR un lenguaje L.Una MT RECONOCE un lenguaje L, si dada una entrada (w) en la cinta, la MT SIEMPRE se para, y lo hace en un EF si y sólo si: w ∈ L

Una MT ACEPTA un lenguaje L, si dada una entrada (w) en la cinta, la MT se para en un Estado Final si y sólo si: w ∈ L Así, en este caso, si w ∉ L , la MT podría no parar.

Ejs: MT que reconoce el lenguaje a*b*, MT que acepta el lenguaje anbncn

EJERCICIO 2Dada la siguiente máquina de Mealy, M=({a,b}, {1,2}, {q0,q1,q2}, T, S):

1. Identifique los componentes de la Máquina (descríbala). 2. Diséñela en diagrama (Máquina de Mealy). 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 y justifíquela porque. 5. Ejecute el RunTest a una cadena aceptada que tenga la menos tres símbolos 6. Identifique en que momento la máquina se detiene. 7. Explique cinco características de la Máquina de Mealy y encuentre cinco

diferencias con las Máquinas de Turing (MT).

Punto 1: Identifique los componentes de la Máquina (descríbala). Los componentes de la máquina de Mealy son 6-tupla: M = (Q, ∑, Γ, q0, δ, β)

En donde:Q = 3 Estados {q0, q1,q2}∑ = Alfabeto de entrada {a,b} Γ = Alfabeto de salida {1,2}q0 = Estado inicial que pertenece a Qδ = Función de Transición β = Función de salida

Punto 2: Diséñela en diagrama (Máquina de Mealy).

Punto 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.

Damos ingreso por el estado inicial q0 con el alfabeto de entrada “aaabbb”.

La secuencia indica que al ingresar “aaa” se mantiene en el estado q0, En la cinta se reemplaza la a por 1.

En la secuencia al llegar a la b cambia al estado q2, en la cinta se reemplaza la b por 2.

En la secuencia al llegar nuevamente a la b cambia al estado q1, en la cinta se reemplaza la b por 1.

En la secuencia al llegar una vez más a la b se mantiene en el estado q1 y en la cinta se reemplaza la b por 2 y para el presente ejercicio finaliza la sesión.

Punto 4: Identifique una cadena que no sea válida y justifíquela porque.

Damos ingreso por el estado inicial q0 con el alfabeto de entrada “ab2”.

La secuencia indica que al ingresar “a” se mantiene en el estado q0, En la cinta se reemplaza la a por 1, luego acepta la entrada “b” y pasa al estado q2, en la cinta se reemplaza la b por 2. Cuando llega a la entrada “2” se presenta el error, la ME no reconoce la cadena, por lo tanto no continúa el recorrido.

Punto 5: Ejecute el RunTest a una cadena aceptada que tenga al menos tres símbolos

Punto 6: Identifique en que momento la máquina se detiene.

En la ME se evidencia que se detiene en el momento que encuentra una entrada que no corresponda con el alfabeto de entrada definido al inicio de igual forma no reconoce símbolos, números ni espacios como entradas.

Punto 7: Explique cinco características de la Máquina de Mealy y encuentre cinco diferencias con las Máquinas de Turing (MT).

CARACTERISTICAS- MEALY DIFERENCIAS ENTRE MEALY - TURING

1. Es una máquina de estados finita.

2. Las salidas están determinadas por el estado actual y la entrada.

3. En el diagrama de estados se incluye una señal de salida para cada arista de transición.

4. Para cada Máquina de Mealy hay una máquina de Moore equivalente y viceversa.

5. Las máquinas de Mealy suministran un modelo matemático rudimentario para las máquinas de cifrado

1. Mealy:La salida depende del estado actual y de las entradas

2. Turing: La salida depende sólo del estado actual

3. Mealy: Por lo regular, tienen menos número de estados

4. Turing: El número de estados es mayor o igual a la máquina de Mealy

5. Mealy: Es menos estable 6. Turing: Es mas estable 7. Mealy: Las salidas se

encuentran en la arista 8. Turing: Las salidas se

encuentran dentro del estado

EJERCICIO 3

Actividades a desarrollar:

1. Realice la conversión paso a paso de la máquina de Mealy del ejercicio del punto a la máquina de Moore equivalente. Se debe realizar la explicación de cada paso que se realice.

Comenzaremos el proceso de conversión a una máquina de Moore equivalente:

MO1 = ({a, b}, {1 , 2}, Q´, T´, S´)

donde: 

T(q0, a) = q0  ,    S(q0, a) = 1  Entonces:

                        q01    Q’ ;   S´( q01)  =  1  ;  T´( q01 , a ) =  q01  ;  T´( q02 , a) =  q01 

T(q0, b) = q2  ,    S(q0, a) = 2   Entonces:

                        q22    Q’ ;   S´( q22)  =  2  ;  T´( q01 , b ) =  q22 ;  T´( q02 , b ) =  q21 

T(q1, a) = q0 ,    S(q1, a) = 1   Entonces :

                        q01    Q’ ;   S´( q01)  =  1  ;  T´( q11 , a ) =  q01 ;  T´( q12 , a ) =  q01 

T(q1, b) = q1  ,    S(q1, b) = 2   Entonces:

                        q12    Q’ ;   S´( q12)  =  2  ;  f´( q11 , b) =  q12 ;  T´( q12 , b) =  q12 

T(q2, a) = q0  ,    S(q2, a) = 2   Entonces:

                        q02    Q’ ;   S´( q02 ) =  2  ;  T´( q21 , a ) =  q02 ;  T´( q22 , a ) =  q02 

T(q2, b) = q1  ,    S(q2, b) = 1   Entonces:

                        q11   Q’ ;   S´( q11)  =  1  ;  T´( q21 , b ) =  q11 ;  f´( q22 , b ) =  q11 

Q´ =  { q01  , q21 , q01 , q02 , q11 },vemos que el estado q21, nunca ha sido creado, por lo tanto se anularán todas las transiciones correspondientes a dicho estado.

    Función Transición  T´

      Función Salida S’

T ´ a b     S´  

q01 q01 q22     q01 1

q22 q02 q11     q22 2

q12 q01 q22     q12 2

q02 q01 q22     q02 2

q11 q01 q12     q11 1

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

Una máquina de Moore es una séxtupla MO = (Q,Σ,∆,δ,λ,q0) donde

Q es un conjunto finito a cuyos objetos seguimos llamando estados.

Σ es un alfabeto que llamamos alfabeto de entrada.

∆ es otro alfabeto que llamaremos alfabeto de salida.

q0 es un elemento de Q que llamamos estado inicial.

δ es una aplicación de Q×Σ en Q que llamamos función de transición.

λ es una aplicación de Q en ∆ que llamamos función de salida.

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

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

La maquina la recorremos con la siguiente cadena aaabaaab

Iniciamos el recorrido en el estado q01/1

hasta leer la cadena aaa el recorrido se mantiene en estado q01/1 y nos muestra en nuestra cinta 1111.

Al leer aaab nos muestra en la cinta 11112 y ahora nos encontramos en el estado q22/2

Al leer aaaba nos muestra en la cinta 111122 y ahora nos encontramos en el estado q02/2

Al leer aaabaa nos muestra en la cinta 1111221 y ahora nos encontramos en el estado donde iniciamos el recorreido q01/1

hemos terminado de leer la cadena aaabaab nos muestra en la cinta 11112212 y ahora nos encontramos en el estado q22/2.

5. Identifique una cadena que no sea válida y justifíquela porque.

cadena a ejecutar ab1

La cadena ejecutada nos es válida porque 1 no ha parte del alfabeto del autómata.

6. Ejecute el RunTest a una cadena aceptada que tenga el menos cinco símbolos

La cadena ejecutada es ababaab

7. Identifique en que momento la máquina se detiene.

La maquina se detienen cuando haya recorrido una cadena aceptada