Grupo_301405_31.docx

EJERCICIOS PLANTEADOS SOBRE MÁQUINAS DE TURING

INTEGRANTES GRUPO SANDRA LLERLY CARDOZO – COD: JHONNY CAICEDO VELARDE – COD: 94329937 MARIO ANDRES QUINTERO – CODIGO: ABRAHAM TREJOS – CODIGO:

TUTOR: LUIS ERNESTO BONILLA ORDUZ

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA AUTOMATAS Y LENGUAJES FORMALES 2018

CONTENIDO

INTRODUCCIÓN .......................................................................... Error! Bookmark not defined. DESARROLLO ACTIVIDADES COLABORATIVAS ............................................................ 3 Desarrollo Ejercicio 1................................................................................................................. 3 Desarrollo Ejercicio 2................................................................................................................. 7 Desarrollo Ejercicio 3............................................................................................................... 13 CONCLUSIONES........................................................................... Error! Bookmark not defined. BIBLIOGRAFÍA.......................................................................................................................... 17

DESARROLLO ACTIVIDADES COLABORATIVAS El trabajo se desarrolla demostrando el procedimiento realizado paso a paso. Desarrollo Ejercicio 1

Diseñe una MT que se comporte como reconocedor que su lenguaje aceptado sea el conjunto de cadenas con el mismo número de ceros que de unos.

1. Identifique los componentes de la Máquina de Turing (descríbala). 1. Identifique los componentes de la Máquina de Turing (descríbala). (𝑎, 𝑏, 𝑐) = 𝑎𝑙𝑓𝑎𝑏𝑒𝑡𝑜 𝑑𝑒 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 (0, 1, 2) = 𝑎𝑙𝑓𝑎𝑏𝑒𝑡𝑜 𝑑𝑒 𝑠𝑎𝑙𝑖𝑑𝑎 (𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞4) = 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑒𝑠𝑡𝑎𝑑𝑜𝑠 Una máquina de Turing con una sola cinta puede definirse como una 7-tupla  Definimos una máquina de Turing sobre el alfabeto, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, posiciona el cabezal sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.  Un cabezal que puede leer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una (y sólo una) celda a la vez. En algunos modelos el cabezal se mueve y la cinta es estacionaria.  Un registro de estado que almacena el estado de la máquina de Turing, uno de los estados finitos. Hay un estado inicial especial con el que el registro de estado se inicia. Turing escribe que estos estados reemplazan el "estado de la mente" en que ordinariamente estaría una persona realizando cálculos.  Una tabla finita de instrucciones (llamada ocasionalmente como tabla de acción o función de transición).

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

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. La cadena de entrada es a

En la primera entrada reemplaza a “a” por 1 y avanza a la derecha.

Luego reemplaza en blanco y se devuelve en la cinta a la izquierda.

Luego reemplaza a 1 por b y avanza a la derecha

Luego reemplaza el espacio por una b y avanza a la izquierda Luego avanza a la izquierda reemplazando a b por b Luego avanza a la derecha sin reemplazar y termina la lectura.

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

La cadena no válida es ab, puesto que el solo debe leer un lenguaje donde sea solo a o aa y no debe ser ab o viceversa.

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

Desarrollo Ejercicio 2 Teniendo en cuenta la siguiente tabla de transición de una máquina de Mealy, realice:

f Estado

Entrada 0

1

q0

q1

q0

q1

q3

q0

q2

q1

q2

q3

q2

q1

G Estado

Entrada 0

q0

1

0

q1

1

1

q2

0

1

q3

0

1

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

Q: {0, q1, q2, q3} En: {0, 1} Sal: {0, 1} Tran: T Res: S Q0: Q0

1

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.

Recorriendo la cadena valida: 0011 La máquina se posiciona en el estado inicial q0, y analiza el primer símbolo de entrada “0” se cambia el símbolo 0 por 1 y pasa al estado q1

Estando en q1 lee el símbolo de entrada 0 y lo cambia por 1 y pasa al estado q3

Estando en q3 lee el símbolo de entrada 1 y lo cambia por 0 y pasa al estado q1

Estando en q1 lee el último símbolo 1 y lo cambia por 1 quedando en q0, entonces se termina la cadena y es aceptada. La cadena ingresada fue 0011, y la cadena de salida es 1101

4. Realice la conversión paso a paso de máquina de Mealy a máquina de Moore

Teniendo en cuenta que la máquina de Mealy ME= ({ 0,1} , { 0,1} , {q0, q1, q2, q3}, T, S)

f Estado

Entrada 0

1

q0

q1

q0

q1

q3

q0

q2

q1

q2

q3

q2

q1

Entrada Estado

0

1

q0

1

0

q1

1

1

q2

0

1

q3

0

0

Comenzando el proceso de conversión a !na máquina de Moore equivalente

MO = ({0,1}, {0,1}, { Q´, T´, E´}

Donde t (q0,0) = q1,E (q0,0) = 1 entonces 𝑞11 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞11 ) = 1 ; 𝑡 ′ (𝑞01 , 0) = 𝑞01 ; 𝑡 ′ (𝑞02 , 0) = 𝑞11 t (q0,1) = q0,E(q0,1) = 2 entonces 𝑞02 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞02 ) = 2 ; 𝑡 ′ (𝑞01 , 1) = 𝑞02 ; 𝑡 ′ (𝑞02 , 1) = 𝑞02 t (q1,0) = q3,E (q1,0) = 1 entonces 𝑞31 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞31 ) = 1 ; 𝑡 ′ (𝑞11 , 0) = 𝑞31 ; 𝑡 ′ (𝑞12 , 0) = 𝑞31 t (q1,1) = q0,E (q1,1) = 2 entonces 𝑞02 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞02 ) = 2 ; 𝑡 ′ (𝑞11 , 1) = 𝑞02 ; 𝑡 ′ (𝑞12 , 1) = 𝑞02 t (q2,0) = q1,E (q2,0) = 1 entonces 𝑞11 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞11 ) = 1 ; 𝑡 ′ (𝑞21 , 0) = 𝑞01 ; 𝑡 ′ (𝑞22 , 0) = 𝑞11 t (q2,1) = q1,E (q2,1) = 2 entonces 𝑞02 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞02 ) = 2 ; 𝑡 ′ (𝑞11 , 1) = 𝑞02 ; 𝑡 ′ (𝑞12 , 1) = 𝑞02 t (q3,0) = q1,E (q3,0) = 1 entonces 𝑞21 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞21 ) = 1 ; 𝑡 ′ (𝑞31 , 0) = 𝑞21 ; 𝑡 ′ (𝑞32 , 0) = 𝑞21 t (q3,1) = q1,E (q3,1) = 1 entonces 𝑞12 ∈ 𝑄 ′ ; 𝑆 ′ (𝑞12 ) = 2 ; 𝑡 ′ (𝑞31 , 1) = 𝑞12 ; 𝑡 ′ (𝑞32 , 1) = 𝑞12 Nos quedara entonces Q’= {𝑞02 𝑞11 , 𝑞12 , 𝑞21 , 𝑞31 } vemos entonces que los estados Nunca fueron creados 𝑞01 , 𝑞22 , 𝑞32 . Por lo tanto se anularan todas las transacciones que correspondan a dichos estados.

5. Explique cinco características de la Máquina de Mealy y encuentre cinco diferencias con las Máquinas de Moore. a) las máquinas de Mealy son esencialmente traductoras porque si recibe una palabra en la entrada recibe otra en la salida. b) contiene un conjunto finito de estados, gracias a ello estos son capaces la palabra en cada instante del dato de entrada leído en el tiempo, por tanto cambia de estado y produce una salida. c) En las máquinas de Turing las salidas se encuentran determinadas por el estado actual y la entrada; esto quiere decir que en su diagrama de estados se debe incluir una señal de salida para cada arista de transición. d) las máquinas de Mealy no posee estados finales. e) las máquinas de Melay es un autómata finito pero la diferencia es que genera una salida, es definida por una 6-tupla.

Desarrollo Ejercicio 3

Desarrolle el siguiente ejercicio: Asuma que hubo error en el dato recibido en el par de bits codificados 2, 5 y 8 con distancia de haming.

Teniendo en cuenta que el dato de entrada es: 00111100 1. 2. 3. 4.

Realice el diagrama de árbol. (Complete la tabla) Realice el diagrama de estados para ese dato de entrada. Identifique en el diagrama de Trellis la ruta correcta (identificando salidas codificadas). Realice el diagrama de Viterbi corrigiendo el dato (ruta correcta).

TABLA DE DATOS, ESTADOS Y DATOS CODIFICADOS

Realice el diagrama de árbol.. (Complete la tabla)

Bit (posición dada en el orden que entran, asociado a K) 8

7

6

5

4

3

2

1

Datos

1

1

0

1

0

0

0

1

Estado presente

11

01

01

10

11

00

01

11

Codificado

10

01

01

11

00

11

11

11

Recibido

11

01

01

10

00

11

10

11

Realice el diagrama de estados para ese dato de entrada

Identifique en el diagrama de Trellis la ruta correcta (identificando salidas codificadas).

Realice el diagrama de Viterbi corrigiendo el dato (ruta correcta).

Llevamos los datos de entrada.

BIBLIOGRAFÍA

Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. Recuperado de: http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&db=nlebk&AN=318032&lang=es&site=edslive&ebv=EB&ppid=pp_Cover

Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1 -124). Recuperado de: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=10566114&ppg=10

Alfonseca C, E., Alfonseca M, M., Mariyón S, R. (2009). Teoría de autómatas y lenguajes formales. (pp. 7-797). Recuperado de: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=10498456&ppg=6

Rosenfeld, D. (2016). Computabilidad, Complejidad computacional y verificación de programas. (pp. 7 - 27). Recuperado de: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=11201616&ppg=12