AUTOMATAS Y LENGUAJES FORMALES

AUTOMATAS Y LENGUAJES FORMALES

Actividad colaborativa

Ejercicio 1:

Teniendo en cuenta el siguiente autómata realizar el proceso de minimización. Se debe realizar el procedimiento paso a paso.

1. Realice la descripción (notación) (caracterización) matemática del autómata. (Antes de minimizar)

2. Plasme la tabla de transición del autómata. (No es la que generas VAS). (Antes de minimizar)

3. Identifique El Lenguaje que reconoce. (Antes de minimizar)

4. Identifique los estados Distinguibles y los No distinguibles.

5. En el proceso de eliminación de estados, identifique que transiciones se eliminan y cuáles se re direccionan. Muestre la tabla de estados distinguibles Para el autómata ya minimizado:

6. Realice la descripción (notación) (caracterización) matemática del autómata ya minimizado

7. Identifique El Lenguaje que reconoce.

8. Identifique su gramática (de forma manual) por la derecha y caracterícela.. Debe incluir el diagrama de estados con los componentes de la gramática asociados a las variables y a las constantes.

Ejercicio 2:

Diseñe un AP que lea el siguiente lenguaje L ={(ab*) | (c*d*)} ; es decir todas las combinaciones posibles de cadenas conformadas por los símbolos (a)
(b*) o (c*)(d*) (con pila vacía).

1. Describa el autómata en notación matemática.

2. Determine el lenguaje que reconoce el AP.

3. Justifique y asocio o evidencie si el diseño es un APND o un APD.

4. Grafíquelo en JFLAP y realice el “Traceback” para las transiciones. (Las columnas para un AP son: El estado en que se encuentra el autómata, lo que falta por leer de la palabra de entrada, y el contenido de la pila).

5. Plasme las imágenes del recorrido de ese Traceback para cada movimiento en el documento. (Se debe apoyar en JFLAP) (Documente el proceso)