AUTOMATAS FASE 2

 

AUTÓMATAS Y LENGUAJES FORMALES

Problemas a desarrollar:

PARTE 1: 

HALLAR EL AUTÓMATA MÍNIMO CORRESPONDIENTE al autómata finito que representa la siguiente expresión regular Expresión regular.

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 la ER y en una tabla de validación (puede ser de Excel), verifique una cadena válida y una no válida. Tenga en cuenta la jerarquía de operadores. (Antes de minimizar)

5. Identifique los estados Distinguibles y los No distinguibles

6. Identifique los estados equivalentes (para ello muestre cómo evalúa esas equivalencias, colocando a los estados candidatos de equivalencia como estados iniciales). Evidencie el proceso de cómo los evalúa.

7. En el proceso de eliminación de estados, identifique que transiciones se eliminan y cuáles se redireccionan. Muestre la tabla de estados distinguibles

8. El autómata nuevo minimizado expresarlo o graficarlos en un diagrama de moore

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

10. Identifique El Lenguaje que reconoce. (autómata ya minimizado)

11. Identifique la ER del autómata ya minimizado y en una tabla de validación (puede ser de Excel), verifique una cadena válida y una no válida. Tenga en cuenta la jerarquía de operadores. (autómata ya minimizado)

12. (Autómata minimizado) 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.

13. Realice la gramática por la izquierda (de forma manual) y compare si esta gramática acepta o no el mismo lenguaje (cadenas). Justifique y demuestre su respuesta.

14. Con una cadena válida, genere un árbol de derivación para la gramática por la derecha y demuestre y justifique si la cadena y árbol generado puede ser ambigua o no.

[ PASO A PASO ]
 
PARTE 2: 

Diseñe un AP que dentro de su lenguaje L ={ (aUb) + (a|b)} ;es decir todas las combinaciones posibles de cadenas conformadas por los símbolos (a) (b) o conjunto universal de estrellas de kleene, (con pila vacía): exceptuando o rechazando cadenas como:

Cadenas no válidas.

• Las que estén compuestas por uno o muchos símbolos “a”: ejemplo: {(a) (aa) (aaa) (aaaa)(aaaaa) (aaaaaa) ....... }
  

• En el diseño que haga es libre determinar si acepta la cadena vacía o no.

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)

6. Muestre el diagrama correspondiente de estados.

7. Determine si su diseño acepta o no la cadena vacía y explique por qué en cualquier caso, demostrando el recorrido o comportamiento de la Pila para ese evento. (evidenciándolo).

[ PASO A PASO ]