Construccion de afd

CONSTRUCCION DE UN AFD A PARTIR DE UNA EXPRESION REGULAR
Para construir un AFD a partir de una expresión regular lo primero que se debe de hacer es construir un árbol sintáctico T para (r)# ydespués se calculan cuatro funciones: anulable, primerapos, ultimapos y siguientepos. Por último se construye el AFD a partir del siguientepos(en la cual se definen un símbolo de entrada). Las funcionesanulable, primerapos, ultimapos se definen sobre los nodos del árbol sintáctico y se usan para calcular siguientepos, que se definen en el conjunto de posiciones.
Los estados significativos de AFNtiene una equivalencia con las posiciones de las hojas en el árbol sintáctico de la expresión regulas, se puede abreviar la construcción del AFN construyendo el AFD cuyos estados corresponden a conjuntosde posiciones en el árbol.
En cada nodo n del árbol sintáctico de una expresión regular, se define la función primerapos(n) que proporciona el conjunto de posiciones que pueden concordar con elprimer símbolo de una cadena generada por la subexpresion con raíz en n. ultimapos(n) proporciona el conjunto de posiciones que pueden concordar con el ultimo símbolo en esa cadena.
A los nodos que sonraíces de las subexpresiones que generan los lenguajes que concluyen la cadena vacía se les denomina anulables.
anulable, primerapos, ultimapos para estas expresiones hay una regla base acerca deexpresiones de un símbolo y tres inductivas(unión, concatenación y cerradura) que permiten determinar el valor de las funciones que constituyen el árbol sintáctico.
Reglas para anulable:
* si n esuna hoja etiquetada con £ entonces anulable(n) es verdadera.
* si n es una hoja etiquetada con un símbolo del alfabeto, entonces anulable(n) es falsa.
* si n es un nodo-ast con hijo c1, entoncesanulable(n) es verdadera.
Regla para primerapos:
* si n es un nodo-cat con hijo izquierdo c1 e hijo derecho c2, y si anulable(c1) es verdadera entonces: primerapos=primerapos u primerapos...