Fase Individual Mario Martinez.docx

EJERCICIOS DE LA FASE 4 ACTIVIDAD INDIVIDUAL

AUTOMATAS Y LENGUAJES FORMALES 301405_22

Tutor a: CESAR JIMENEZ

Presentado por: Mario Martinez Código: 1032399424

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA NOVIEMBRE 2018 BOGOTÁ

Tabla de contenido Actividad 1 ................................................................................................................................................................... 3 Actividad 2 ................................................................................................................................................................. 11 Actividad 3 ................................................................................................................................................................. 25 Bibliografía ................................................................................................................................................................ 28

Actividad 1 De acuerdo con el último dígito de su cédula o tarjeta de identidad, identifique el ejercicio asignado en la siguiente tabla: Último dígito de la Cédula o TI 1y9 2y8 3y7 4y6 5y0

Ejercicio Ejercicio Ejercicio Ejercicio Ejercicio Ejercicio

1 2 3 4 5

ACTIVIDAD 1: Maquinas de Turing 1. Ejercicio 1

2. Ejercicio 2

3. Ejercicio 3

4. Ejercicio 4

5. Ejercicio 5

Aporte presentando por: Mario Martinez Garzón El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: EJERCICIO POR TRABAJAR Caracterización de la máquina de Turing

En este espacio se realiza: Las características de la máquina de Turing:  Es un dispositivo de reconocimientos de lenguaje, es más general que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto los lenguajes regulares, como los lenguajes independientes de contexto y además muchos otros tipos de lenguajes.  Tiene, un control finito, un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.  Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada.  El cómputo es determinado a partir de una tabla de estados de la forma: (estado, valor) (nuevo estado, nuevo valor, dirección)  La máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario. - Realizar un cuadro donde explique las diferencias y similitudes de las máquinas reconocedoras y Transductores.

Maquina

Diferencia s

Reconocedor a la cinta puede quedar con cualquier cosa y el cabezal también puede quedar en cualquier posición Si la cadena es aceptada, la máquina pare en un estado final Determina si la cadena es válida o no, según algún criterio. Rreconoce un lenguaje L, si para cualquier entrada en la cinta, w, se acaba parando, y lo hace en un estado final si y sólo si w Є L. Acepta un lenguaje L, si al analizar una palabra w, se para

Transductora

Se puede considerar que una máquina de Turing computa una determinada función sobre una cadena (o un conjunto de ellas) en lugar de computarla sobre un conjunto de enteros. Convierten una secuencia de señales de entrada en una secuencia de salida, pudiendo ser binaria o mucho más compleja, dependi entrada actual. Son de mayor interés en la electrónica digital y la computación práct

en un estado final si y sólo si w Є L. Ambos tipos de máquinas siguen siendo Autómatas, las Transductoras son una variación de las Aceptadoras. En estas máquinas existe una función (la llamaremos función de salida) que puede tomar como parámetro el estado actual o la transición de Similitudes nuestra máquina y arroja un elemento del conjunto de símbolos de salida. Existe otra función (la llamaremos función estado) que nos indicará el estado siguiente que deberá adoptar nuestra máquina según el carácter leído de la cadena de entrada y el estado. Procedimiento de paso a paso del recorrido de una cadena

Realice de manera detallada y grafica el procedimiento paso a paso del recorrido de una cadena (La cadena la selecciona el estudiante, debe contener como mínimo 10 caracteres) en la máquina de Turing. Describir cómo funciona el almacenamiento mediante el uso de las cintas, etc. Realizar la representación utilizando flechas, conexiones, diagramas que permitan ver el funcionamiento de la máquina de Turing transición por transición δ(q0,1)=(1,R,q0) - Paso 1: Inicialmente la maquina realiza el proceso por medio de un bucle, estamos en el estado q0. Si encuentra un 1, deja 1 y se dirige hacia la derecha quedando en q0. δ(q0,1)=(1,R,q0) Si encuentra un 0, se deja en 0 y se dirige a la derecha, pero no se almacena en la cinta, porque no es el símbolo que tiene que leer la máquina para los input (entrada)

- Paso 2: Se repite el mismo procedimiento que el paso 1, pero esta vez se saltan los símbolos 1 hasta encontrar un 1 (que debe existir) y se dirige hacia la derecha. Quedando de la siguiente manera:

- Paso 3: Ahora cuando en el estado q0 se encuentra, se deja en y se pasa hacia la izquierda quedando en el estado q1. δ(q0,𝜹)=(𝜹,L,q1) - Paso 4: Si en q1 se encuentra un 1, se deja 0 y se pasa a la izquierda quedando en el estado q2. Este carácter se almacena en la cinta como output (salida). δ(q1,1)=(0,L,q2)

Paso 4: Si en q2 se encuentra un 1, se deja 0 y se pasa a la izquierda quedando en el estado q2. Este carácter se almacena en la cinta como output (salida). δ(q2,1)=(0,L,q2)

- Paso 5: Se repite el mismo procedimiento que el paso 4, pero esta vez se saltan los símbolos 0 hasta encontrar un 0 (que debe existir) y se dirige hacia la izquierda. Quedando de la siguiente manera:

- Paso 6: Si en el estado q2 se encuentra un 𝜹, se deja en 1 y se pasa hacia la Derecha quedando en el estado q1. δ(q2,𝜹)=(1,S*,q3)! Entonces quedaría la cinta de la siguiente manera:

Y Tendríamos como resultado final: Input: 1111111111 Output: 1000000000 Practicar y verificar lo aprendido

Apoyándose en el simulador JFlap o VAS ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechazadas por la máquina. En este espacio adjunta la imagen.

Rechazadas

1000

101

00011

10101

110111

ACEPTADAS

1

11

111

1111

11111

Actividad 2 Teniendo en cuenta la siguiente tabla de transición de una máquina de Mealy, realice: F Estado q0 q1 q2 q3

Entrada 0 1 q1 q0 q3 q0 q1 q2 q2 q1

G Estado q0 q1 q2 q3

Entrada 0 1 1 0 1 1 0 1 0 1

1. Identifique los componentes de la Máquina (descríbala). Los componentes de la máquina de Mealy son 6-tupla: M = {S, S 0, Σ, Λ, T, G} Q = 4 Estados {q0, q1, q2, q3} Σ =Alfabeto de entrada {0,1} Г = Alfabeto de salida {0,1} q0= Estado inicial que pertenece a Q δ = Función de transición β = Función de salida

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. A continuación, observaremos el recorrido paso a paso de la cadena 1001001011 en donde probaremos que nuestra maquina la aceptara como válida. En la siguiente imagen nos encontramos con nuestro maquina en estado inicial, eso quiere decir sin haber recibido el primer carácter de la cadena.

En la primera imagen se verá reflejada Paso a paso cadena 1001001011 Actividad 2, paso cero. Se inicia el estado en q0 el cual es 1, la maquina valida la información brindada y da un símbolo del alfabeto de salida que para este caso es 0, el cual se está viendo reflejado en una cinta de transición y seguimos en el estado q0, como lo indica la transición.

Segunda imagen Paso a paso cadena 1001001011 actividad 2, paso uno. Se ingresa el símbolo 0, la maquina vuelve a validar la condición y en esta ocasión nos trasladamos al estado q1 y nos genera una solución de salida con símbolo 1 el cual se ve reflejado en la cinta de transición.

Tercera imagen Paso a paso cadena 1001001011 actividad 2,

paso dos.

Se siguen ingresando más símbolos a la cadena, en este momento se va a ingresar nuevamente otro 0 el cual va a permitir pasar al estado q3 y con un símbolo de salida 1, el cual almacena una 5 validación.

Cuarta imagen paso a paso a paso cadena 1001001011 actividad 2, paso tres

Se ingresa el símbolo número 1 el cual es válido y nos desplazamos al estado q1 como nos indica la transición y nos genera un símbolo de salida 0.

Quinta imagen Paso a paso cadena 1001001011 Actividad 2, paso cuatro. Se ingresa otro 0 de nuestra cadena a validar y esto permite retomar el estado q3 tal cual como lo indica el proceso de transición de nuestro diagrama jflap, retomando un valor de salida de 1 el cuan se observa en la cinta.

Sexta imagen Paso a paso cadena 1001001011 Actividad 2, paso cinco Se ingresa un nuevo símbolo el cual es 0, luego se pasa del estado q3 al estado q2 según nuestro proceso de transición así mismo, nos va a generar un símbolo de salida de 1.

Séptima imagen paso a paso cadena 1001001011 Actividad 2, paso seis. Estando en el estado q2 nuestra maquina detecta un nuevo símbolo de entrada el cual es 1, por lo tanto, al ser validado y siguiendo las reglas de nuestras transiciones nos quedamos nuevamente en el mismo estado actual, pero con el símbolo de entrada se genera un símbolo de salida que es 1

Octava imagen paso a paso cadena 1001001011 Actividad 2, paso siete. Para pasar del estado q2 al estado q1 como lo indica la transición, la maquina recibe como símbolo de entrada el 0 y este a su vez generaría un símbolo de salida de 0.

Novena imagen Paso a paso cadena 1001001011 Actividad 2, paso ocho. Al ingresar el símbolo 1 de nuestro alfabeto de entrada, la maquina se desplaza al estado q0, generando un símbolo de salida de 1; el cual cómo podemos evidenciar se almacena en la cinta y de esta manera se nos está generando otra cadena y esto se debe a que por cada símbolo de entrada él nos da un símbolo de salida diferente o igual al de entrada.

decima imagen Paso a paso cadena 1001001011 Actividad 2, paso nueve. Para terminar la máquina de Mealy detecta que ha ingresado el ultimo 1 de la cadena a validar, esta genera un carácter de salida el cual es 0 y al no existir más caracteres la cadena se valida y es aceptada; quedando en la cinta la siguiente cadena de salida 0110111010.

Onceava imagen Paso a paso cadena 1001001011 Actividad 2, paso diez. 4. Realice la conversión paso a paso de máquina de Mealy a máquina de Moore Creamos una tabla para interpretar los estados y las salidas MAQUINA DE MEALY 0 q0 q1 q2 q3

ESTADO q1 q3 q1 q2

SALIDA 1 1 0 0

1 ESTADO SALIDA q0 0 q0 1 q2 1 q1 1

Q0 cuando ingres un 0 pasa al estado q1 y la salida es 1, cuando q0 ingresa 1 pasa a un estado q0 y salida 0. Ahora pasamos la tabla de estados y salidas de la máquina de Mely a la máquina de Moore. Creamos una tabla con los posibles estados de la máquina de Mely.

posibles estados q0 q11 q00 q31 q01 q10 q21 q20 Ahora creamos la tabla de la máquina de Moore con los posibles estados

q0 q11 q00 q31 q01 q10 q21 q20

Máquina de Moore 0 estado salida q11 1 q31 1 q11 1 q20 0 q11 1 q31 1 q10 0 q10 0

estado q00 q01 q00 q11 q00 q01 q21 q21

1 salida 0 1 0 1 0 1 1 1

Luego creamos las tablas individuales de función de transición y salida: función de transición T q0 q11 q11 q31 q00 q11 q31 q20 q01 q11 q10 q31 q21 q10 q20 q10

0

función de salida G 0 q0 1 q11 1 q00 1 q31 0 q01 1 q10 1 q21 0 q20 0

1 q00 q01 q00 q11 q00 q01 q21 q21

1 0 1 0 1 0 1 1 1

Ahora creamos el diagrama en jflap:

Luego creamos la máquina de Moore graficando con jflap con la tabla de transicion que hemos creado:

Tabla:

q0 q11 q00 q31 q01 q10 q21 q20

Máquina de Moore 0 estado salida q11 1 q31 1 q11 1 q20 0 q11 1 q31 1 q10 0 q10 0 Graficamos

estado q00 q01 q00 q11 q00 q01 q21 q21

1 salida 0 1 0 1 0 1 1 1

Luego simulamos la cadena de caracteres, hacemos un test con la cadena 100001 y vemos que son equivalentes:

5. Explique cinco características de la Máquina de Mealy y encuentre cinco diferencias con las Máquinas de Moore. Características de la Maquina de Mealy: 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.

Ítem

Diferencias entre la

maquina Moore

Mealy

Máquina de Mealy

Máquina de Moore

y

1

La salida depende del La salida depende estado actual y de solo del estado las entradas. actual.

2

Por lo regular Tiene menos números de estados

El número de estados es mayor o igual a la Máquina de Mealy

3

Es menos estable

Es más estable

Para probar un circuito, primero se hace el cambio en la entrada X y después se da el pulso de reloj.

Para probar un circuito, primero se da el pulso de reloj y después se hace el cambio en la entrada X.

Las salidas se encuentran en la arista.

Las salidas se encuentran dentro del estado.

4

5

Actividad 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: 00110100 1. Realice el diagrama de árbol. (Complete la tabla) De acuerdo con el árbol, tenemos los estados presentes y los datos codificados por codificación convoluciones, adicional se identificando la cadena valida de entrada, por lo que se procede a diligenciar la siguiente tabla Tabla resultada de cadena valida, estados presentes y codificación de salida ejercicio 3

Respuesta:

00110100

Diagrama de árbol

2. Realice el diagrama de estados para ese dato de entrada.

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

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

Bibliografía Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. Recuperado http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&db=nlebk&AN=3180 32&lang=es&site=eds-live&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 González, A. [Ángela]. (2018, junio 1). Lenguajes Estructurados por Frases. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18316 CK-12, (2012). Case History: How Math, Science, and Engineering Led to the First Pocket Radio. [OVI]. Recuperado de: http://www.ck12.org/book/Engineering%3A-AnIntroduction-for-High-School/section/5.2/ 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