• Author / Uploaded
• Johan Sebastian Vargas

Citation preview

AUTOMATAS Y LENGUAJES FORMALES UNIDAD 3- FASE 4 – MOELAR PROBLEMAS DE LENGUAJES ESTRUCTURADOS POR FRASES

PRESENTADO POR: Dagnner Susan Castillo Código: 31323697 Jhoan Sebastian Vargas Código: 1144137952 Teresa Escobar Código: 1057547373 Deisy Yolima Cuevas Código: 1054254101 Andrés Mauricio Espinosa Código: 1144042419

PRESENTADO A: Vermen Rainer Ayala

GRUPO: 301405_46

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD INGENIERIA DE SISTEMAS ABRIL DE 2020

DESARROLLO DE LA ACTIVIDAD 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 q2 q0 q3 q2 q2 q1

G Estado q0 q1 q2 q3

Entrada 0 1 1 1 0 1 1 0 0 0

1. Identifique los componentes de la Máquina (descríbala). MM ¿(Q , ∑ , Γ , q 0 , δ , α ) Donde: Q={q 0 , q 1 , q 2 , q 3 } ∑ = {0,1} es el alfabeto de entrada donde ∐ ∉∑ Γ ={ 1 ,0 } es el alfabeto de salida MM = ({ q 0 ,q 1 , q 2 , q 3 } ,{0,1}, {0,1}, q 0 ,δ , α ¿ δ es la función de transición de estados y está definida por: δ ( q 0 , 0 )=q 1 δ ( q 0 ,1 )=q 0 δ ( q 1, 0 )=q 2 δ ( q 1, 1 )=q 0 δ ( q 2 ,0 )=q 3 δ ( q 2 ,1 )=q 2 δ ( q 3 ,0 )=q 2 δ ( q 3 ,1 ) =q 1 

La máquina de Mealy es una tulpa de 6 (S, S0, ∑, Γ , t, G)

S: (q0, q1, q2, q3).

S0 :(q0). ∑ (0.1) Γ (1.0) Una Función de transición (T: S× Σ → S) Una función de salida:(G: S× Σ → Λ) 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 CADENA 0

1

1

0

0

0

0

δ(q0,0)=(q1,1): cambia al estado q1, en la cadena lee 0 y lo cambia por 1: 0 1 1 0 0 0 0

δ(q1,1)=(q0,1): cambia al estado q0, en la cadena lee 1 y lo cambia por 1: 0 1 1 0 0 0 0

δ(q0,1)=(q0,1): sigue en el estado q0, en la cadena lee 1 y lo cambia por 1:

0

1

1

0

0

0

0

δ(q0,0)=(q1,1): cambia al estado q1, en la cadena lee 0 y lo cambia por 1: 0 1 1 1 0 0 0

δ(q1,0)=(q2,0): cambia al estado q2, en la cadena lee 0 y lo cambia por 0: 0 1 1 1 0 0 0

δ(q2,0)=(q3,1): cambia al estado q3, en la cadena lee 0 y lo cambia por 1: 0 1 1 1 0 1 0

δ(q3,1)=(q2,0): cambia al estado q2, en la cadena lee 1 y lo cambia por 0 y finaliza la secuencia: 0 1 1 1 0 1 0 4. Realice la conversión paso a paso de máquina de Mealy a máquina de Moore Realizamos la tabla de la máquina de Mealy: 0 1 Estado Salida Estado Salida q0 q1 1 q0 1 q1 q2 0 q0 1 q2 q3 1 q2 0 q3 q2 0 q1 0 Con base a esta tabla vamos a hacer los posibles estados equivalente (vamos a renombrarlos) para la maquina Moore basándonos en la tabla de arriba: Posibles estados q0 q11 q01 q20 q31

q10

Con estas tablas vamos a proceder a crear nuestra tabla de equivalencia para la maquina Moore. 0 1 Estado Salida Estado Salida q0 q11 1 q01 1 q01 q10 0 q01 1 q10 q11 1 q20 0 q11 q10 0 q20 0 q20 q31 1 q01 1 q31 q10 0 q01 1 Con

base

a

esta

tabla

hacemos

nuestro

diagrama

en

Jflap:

5. Explique cinco características de la Máquina de Mealy y encuentre cinco diferencias con las Máquinas de Moore.

Máquina de Mealy     

Es una maquina con estado finitos Su salida la establece el estado actual En el diagrama de estados, contiene una señal de salida para cada arista de transición. Para cada máquina de Mealy se puede crear una de Moore equivalente. Esta máquina suministra un modelo matemático para las máquinas de cinta.

Diferencias con Moore   

Que la salida en un momento dado sólo depende de su estado en ese momento. El diagrama de estados para una máquina Moore, incluirá una señal de salida para cada estado. incluye una cadena de Lógica combi nacional para decodificar el estado actual en salidas (lambda)

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: 11110101 1. Realice el diagrama de árbol. (Complete la tabla) Cinta con 100

Cinta con 010

Cinta con 101

Cinta con 010

Cinta con 101

Cinta con 110

Cinta con 111

Cinta con 111

Tabla de datos, estados y datos codificados  

Bit (Posición dada en el orden que entran asociado a k)

 

8

7

6

5

4

3

2

1

Datos

1

1

1

1

0

1

0

1

Estado Presente

11

11

11

10

01

10

01

10

Codificado

01

01

10

00

01

00

01

11

Recibido

00

01

10

01

01

00

11

11

Con la tabla de datos completa, procedemos a construir el diagrama de árbol.

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

Bit (Posición dada en el orden que entran asociado a k)

 

8

7

6

5

4

3

2

1

Datos

1

1

1

1

0

1

0

1

Estado Presente

11

11

11

10

01

10

01

10

Codificado

01

01

10

00

01

00

01

11

Recibido

00

01

10

01

01

00

11

11

3. Identifique en el diagrama de Trellis la ruta correcta (identificando salidas codificadas). Con la tabla de datos completa, procedemos a construir el diagrama de Trellis.

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

BIBLIOGRAFÍA Bonilla, L. [Luis] (2018, mayo 23). Diagrama de árbol. [Archivo de video]. Recuperado de https://youtu.be/HNS4IQw64Sk Bonilla, L. [Luis] (2018, mayo 23). Diagrama de estados. [Archivo de video]. Recuperado de https://youtu.be/JTJkNco2tjQ Bonilla, L. [Luis] (2018, mayo 23). Diagrama de trellis. [Archivo de video]. Recuperado de https://youtu.be/21JKzST2ZJY González, A. [Ángela]. (2018, junio 1). Lenguajes Estructurados por Frases. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18316