Compiladores

Compiladores
Práctica 1

Descripción de la práctica
• PRACTICA 1
• Definición: Diseño e implementación de las clases AFN y AFD. • Objetivo: Desarrollar un programa en un lenguaje que useinterfaz gráfica y que tenga como entrada la quíntupla de un autómata determinístico y como salida muestre un AFN o AFD.

Conceptos previos
AUTOMATAS FINITOS • Un autómata finito es un modelo matemáticode una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolosde la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final. • Si para todoestado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún estado y para el mismo símbolo deentrada, se definen dos o más transiciones se dice que el autómata es no determinístico (AFND).

Conceptos previos
Formalmente un autómata finito se define como una 5-upla M = donde: E: conjuntofinito de estados A: alfabeto o conjunto finito de símbolos de entrada d: función de transición de estados, que se define como - d: E x A  E si el autómata es determinístico - d: E x A  P(E) si elautómata es no determinístico (P(E) es el conjunto potencia de E, es decir el conjunto de todos los subconjuntos de E) e0: estado inicial; e0  E F: conjunto de estados finales o estados de aceptación;F  E

Conceptos previos
• Generalmente se asocia con cada autómata un grafo dirigido, llamado diagrama de transición de estados. Cada nodo del grafo corresponde a un estado. El estado inicial seindica mediante una flecha que no tiene nodo origen. Los estados finales se representan con un círculo doble. • Si existe una transición del estado ei al estado ej para un símbolo de entrada a,...