AUTOMATAS Y LENGUAJES FORMALES

 

AUTOMATAS Y LENGUAJES FORMALES

Actividad colaborativa

Ejercicio 1: 

Diseñe una MT que se comporte como transductor que reconozca el lenguaje L={ab*(bc)*}. La transducción (salida) debe ser que por cada símbolo que entre cambie el símbolo del alfabeto de la cinta, de la siguiente manera: a= 0; b=1; c=2.

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

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.

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 cinco símbolos.

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

Ejercicio 2:


Diseñe un Transductor (MAQUINA DE MEALY) que realice la misma transducción del ejercicio anterior.

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. Explique cinco características de la Máquina de Mealy y encuentre cinco diferencias con las Máquinas de Turing (MT).

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

1. Determine cuál fue el dato de entrada. (Complete la tabla)

2. Determine los estados presentes: (represente la máquina de estados) del código convolucional para k=1 , m= 3, n=2 para cada estado, Es decir, represente la transición de entrada para cada bit (ocho en total) con el codificador convolucional.  

3. Estos estados presentes debe completarlos también en la tabla.

4. Determine las salidas codificadas: (Complete la tabla).

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

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

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