MANUAL REDUCIDO JFLAP (Java Formal Language and Automata Package)

1. Introduccin a JFLAP
JFLAP (Java Formal Language and Automata Package) es una herramienta para la enseanza y la visualizacin interactiva de lenguajes formales. Permite crear y operar sobre autmatas (finitos, mquinas de Moore y Mealy, Turing), gramticas, expresiones regulares y L-systems. En esta prctica inicial slo nos vamos a centrar en la parte enfocada a las gramticas, y segn avance el curso, iremos profundizando en los distintos apartados de la aplicacin. Aunque algunas secciones no se vern en la asignatura.

2. Conceptos bsicos de gramticas

Antes de comenzar con la explicacin de la prctica a realizar en esta sesin, se incluye un breve recordatorio de una serie de definiciones y nociones sobre gramticas. Todo esto, visto en clases de teora, ser necesario conocerlo a la hora de utilizar el programa. Una gramtica esta formada por: Elementos terminales (T): Todas las cadenas del lenguaje representado por la G (L(G)), estn formadas con smbolos de este alfabeto. Elementos no terminales (N): Es un conjunto de smbolos auxiliares introducidos como elementos auxiliares para la definicin de G pero que no figuran en las cadenas de L(G). Producciones: Conjunto de reglas de produccin u::=v donde u+ y v* u=xAy tal que x, y * y A N. Axioma: Es un smbolo destacado, no Terminal, a partir del que se comienzan a aplicar las reglas de produccin.

3. Iniciar JFLAP
La herramienta se puede descargar gratis de la url: www.jflap.org (rellenando un formulario previamente), o bien os la podis bajar de aula global. JFLAP est implementado en Java, por lo que es necesario tener la versin Java SE 1.4 o posterior instalada en vuestro ordenador. En el caso de las aulas informticas de la clase de prcticas, ya estar instalado. JFLAP se distribuye como un ejecutable .jar. Para ejecutar este tipo de ficheros en un sistema operativo Windows, basta con hacer doble clic en JFLAP.jar. En el caso de Linux, desde la consola, con el fichero JFLAP.jar en el directorio actual, tendris que introducir el comando java jar JFLAP.jar (este comando funciona de la misma forma en la consola de Windows). Una vez abierta la aplicacin, aparecer en pantalla una interfaz como la que se muestra en la Figura 1. 1

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

Figura 1: Ventana inicial de JFLAP En este caso, slo nos preocuparemos de la parte de JFLAP que nos permite manipular gramticas, por lo que pulsando en Grammar en la interfaz de la Figura 1 pasaris a la ventana del editor.

3.1. Editor de gramticas

En esta ventana, podremos definir las gramticas. En la Figura 2 se observa un ejemplo ya introducido.

Figura 2: Editor de gramticas de JFLAP

Figura 3: Vista de una gramtica guardada con formato xml

Abriendo la opcin File del men, podremos guardar las gramticas en ficheros (en formato xml, Figura 3), cargarlos ms tarde en el programa, imprimirlos, abrir un nuevo editor (puede haber varios abiertos a la vez), cerrarlo, y para el caso en el que haya varias opciones abiertas (editores, brute parse), dismiss tab cerrar la actual. Antes de empezar a manipularlo, hay unas notas sobre el funcionamiento del editor, que tendremos que tener en cuenta: Para escribir en un recuadro especfico del editor, posicionarse y hacer clic sobre l, o bien, utilizando la tecla del tabulador, nos podemos mover por las celdas.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

Cada carcter que escribamos en el editor, ser un smbolo del alfabeto de la gramtica. No se pueden manejar smbolos de ms de un carcter. Al introducir las producciones hay que tener en cuenta, que JFLAP no nos pedir que le digamos cul es el conjunto de los smbolos terminales y el de los no terminales. Esta informacin la deducir en base a las producciones que escribamos en el editor. JFLAP interpretar como smbolos no terminales todos aquellos escritos en maysculas, y como terminales los dems (p.ej.: 4, q, #, a, etc.). El axioma ser siempre el smbolo que escribamos en la parte izquierda de la primera produccin (la primera lnea del editor). Si al escribir una produccin se deja en blanco la parte derecha, el editor entender que produce . JFLAP no acepta notacin de Backus. El tipo de gramtica no se define, ni el editor comprueba que el formato sea correcto, salvo si posteriormente se lleva a cabo alguna operacin no permitida, en cuyo caso aparecer un mensaje de error.

En el ejemplo de la Figura 2, en la que tenemos una gramtica, vemos como el axioma es S, el conjunto de no terminales es {S, A, B, C}, y el de los terminales es {a, b, q, v, x y}. La ltima produccin A , es la nica produccin que hay. Ahora, prueba a escribir esta misma gramtica en tu ventana del editor.

3.2. Brute Force Parser (Derivador por fuerza bruta)

En el men Input, de la ventana del editor de gramticas, vemos la opcin Brute Force Parser. Este operador recoge una palabra que hayamos escrito en el recuadro Input y, segn la gramtica introducida en el editor, derivar la sentencia paso a paso, a travs de reemplazos de no terminales con producciones, mostrando los pasos intermedios del proceso de derivacin. Esos pasos intermedios (llamados formas sentenciales) incluirn elementos terminales y no terminales, hasta que en la ltima sentencia, cuando la palabra es aceptada por la gramtica, la derivacin est formada slo por elementos terminales. Este procedimiento se puede visualizar de dos formas cuando la palabra es aceptada: mediante una tabla de derivacin (Figura 4), o grficamente, con un rbol que es la opcin seleccionada por defecto por la aplicacin (Figura 5)*.

Figura 4: Brute parser con tabla de derivacin

* El rbol de derivacin no debe preocuparnos en la primera clase

Figura 5: Brute parser con rbol de derivacin -3-

Para utilizar esta opcin de la herramienta, habr que introducir la palabra, pulsar el botn Start, y si la palabra es aceptada (aparecer un comentario debajo del recuadro de Input que lo dir), podremos pulsar el botn Step, para que vayan surgiendo los pasos que ha seguido el programa para comprobar que esa palabra era generada por la gramtica. Una palabra puede ser no aceptada por varios motivos: Que la palabra se haya escrito mal, aadiendo un elemento no terminal del alfabeto (las palabras aceptadas por una gramtica estn formadas slo por elementos terminales), o que aparezca un smbolo que no pertenezca al alfabeto de la gramtica introducida en el editor. En este caso, aparecer una ventana con el error. Que la palabra est bien escrita, pero que la gramtica no la pueda generar (no pertenezca al lenguaje). En ese caso, debajo del recuadro de Input, aparecer: String rejected.

3.3. Multiple Brute Force Parse (Derivador Mltiple por fuerza bruta)
Esta opcin es similar a la anterior. La diferencia radica en que en este caso, se puede comprobar la pertenencia de varias palabras a una gramtica de forma simultnea, mientras que antes slo se comprobaba una (Men > Input > Multiple Brute Force Parser).

Figura 6: Ejemplo de derivador mltiple por fuerza bruta En este caso, en la tabla de la derecha (Ver Figura 5), en la columna de Input, aadiremos las palabras que queremos comprobar. Una vez agregadas todas, pulsando en el botn Run Inputs, la herramienta nos dir las palabras aceptadas y las rechazadas tal y como muestra la Figura 6. Si queremos ver la tabla de derivaciones o el rbol de alguna palabra aceptada especficamente, habr que seleccionar la fila correspondiente, y en la parte izquierda de la tabla, pulsar el botn Start y Step, que funcionan del mismo modo que para el caso explicado en el apartado 3.2.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

3.4. Gramticas de contexto libre (G2)

Este tipo de gramticas tienen como caracterstica, que en las producciones hay un solo smbolo no terminal a la izquierda y no tienen restricciones en la parte derecha. Para trabajar con este tipo de gramticas en JFLAP, se seguir el mismo procedimiento que lo explicado para gramticas regulares. En este apartado slo incluiremos algn ejemplo de trucos para facilitar el reconocimiento de los lenguajes que genera una G2. Primero pasamos al editor una gramtica de tipo 2, como la que muestra la Figura 7, y vemos la tabla de derivacin resultado de introducir la palabra aaabbbbbb (Figura 8).

Figura 7: Ejemplo de G2 Figura 8: Tabla de derivacin que acepta la palabra aaabbbbbb Una forma de pensar en la descripcin de todas las palabras que acepta una gramtica, es pensar en qu tipo de palabra puede derivar cada elemento no terminal. En qu puede derivar el axioma S? Fijndonos en las tres primeras derivaciones de la tabla de la Figura 8, S puede derivar en {aSb, aaSbb, aaaSbbb, ...}. Si pensamos en todas las producciones de S, podemos ver otras formas sentenciales en las que S puede derivar, como {bB, abBb, aabBbb, ...}, y podemos sacar la conclusin de que S puede derivar en {anbBbn | n 0}. Si nos fijamos ahora en el smbolo no terminal B, en qu puede derivar? Si modificamos lo que tenemos en el editor, colocando como primera produccin B B, como si fuera el axioma, e introducimos unas cuantas palabras de prueba en el derivador mltiple por fuerza bruta, veremos que B puede derivar en las palabras { , bb, bbbb., bbbbbb, ...}, o expresado de otra forma (bb)*, un nmero par de bs. La combinacin de en que pueden derivar S y B implica que el lenguaje de esta gramtica es {anb(bb)*bn | n 0} Por lo tanto, en JFLAP se puede determinar qu palabras genera un smbolo no terminal A, colocando A como si fuera el axioma. Para simular esto, introduce la primera produccin que hubiera en el editor de tu gramtica original al final de la lista de producciones para guardarla, y entonces introduce A A como la primera produccin. Haz pruebas con varias palabras comprobando las que se aceptan y las que no. Segn los resultados, podrs definir una regla general para el smbolo no terminal A. Si unes estos resultados, a la regla que hayas detectado que genera el axioma original, tendrs el lenguaje que genera la gramtica inicial.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

3.5. Otros tipos de gramticas

Para gramticas de tipo G0 y G1, el editor de JFLAP se comporta igual que en casos anteriores. Se pueden escribir en la parte derecha y en la parte izquierda de la produccin tantos smbolos como tenga la gramtica que queremos introducir sin ningn problema. Y a la hora de ver su tabla o rbol de derivacin, tambin se podr hacer. En la Figura 9 tenemos un ejemplo de esto. Vemos como tres nodos del rbol producen otros tres nodos que forman una palabra del lenguaje de la gramtica definida en el editor.

Figura 9: rbol de derivacin de una G1, que acepta la palabra 101

Figura 10: Ejemplo de cmo sera el archivo de una gramtica 0 en JFLAP

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

3.6 Uso del modo batch

El modo batch es una funcin que tiene JFLAP para poder probar ficheros con gramticas y palabras, cargados desde archivo. De esta forma, se puede hacer un test fcilmente de las palabras que acepta o rechaza una gramtica. Esta funcin puede ser muy til si queremos hacer una comprobacin rpida, si tenemos los archivos guardados y sin usar directamente el derivador mltiple por fuerza bruta. Como ejemplo, usaremos la siguiente gramtica con una lista de palabras: aabbc S aB abc S aA aaabbc A abB abcc B bC aabaabaabaabbc B aA aabaabbc Cc aaabc Para comenzar, introduce la gramtica en el editor de JFLAP y gurdala en el ordenador. Despus, crea un archivo *.txt en una columna con la lista de palabras. Una vez realizados estos dos pasos, en el men inicial de JFLAP pincha en Batch > Batch Test. Se abrir una ventana para que indiques donde se encuentra el archivo que has guardado con la gramtica, y luego otra para que cargues el fichero con las palabras. Acto seguido aparecer una nueva ventana como la de la Figura 16. Pinchando en el botn Run Inputs, JFLAP comprobar para todas las palabras del fichero las que son generadas por la gramtica y las que no lo son, informando del resultado. Entre parntesis aparece la solucin esperada (por defecto, JFLAP espera que todas las palabras cargadas de fichero sean vlidas). Si seleccionamos con el ratn una de las palabras, y pulsamos en el cuadro de la izquierda en Start y Step, aparecer el rbol de derivacin, como en el derivador por fuerza bruta.

Figura 16: ejemplo de uso del modo batch Desde esa misma ventana, podremos: editar la gramtica (Edit File); aadir ms palabras, especificando el resultado que esperamos obtener (Add input string); cargar otro fichero con otra gramtica, y probar la misma lista de palabras para dos gramticas distintas (Add file); guardar los resultados (Save Results); y otras operaciones, algunas de las cuales veremos ms adelante, como limpiar la gramtica, pasar a autmata finito, etc.
Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

4. Limpieza de gramticas
A veces es ventajoso transformar una gramtica en otra equivalente con un formato ms simple. Sobre todo a la hora de aplicar algn algoritmo sobre la gramtica (como el Brute Force Parser), para que la operacin sea ms rpida y eficiente. JFLAP tiene implementados cuatro algoritmos de limpieza de gramticas. Las tres primeras transformaciones eliminan las producciones (reglas no generativas), las reglas de redenominacin (tipo A B) y las reglas superfluas, respectivamente, y la cuarta transforma la gramtica resultado de lo anterior a una gramtica en Forma Normal de Chomsky (FNC). JFLAP requiere que esas cuatro transformaciones se realicen en este orden, ya que al eliminar las producciones , pueden aparecer reglas de redenominacin, y eliminar estas puede generar reglas superfluas. JFLAP se saltar alguno de estos pasos en caso de que no sea necesario realizarlo. Slo se consideran gramticas de contexto libre que no deriven en , porque la palabra vaca slo aparece en casos especiales y es fcil eliminarla del lenguaje, y aadirla de nuevo a la gramtica resultante despus de la transformacin. Dado que jflap realiza la limpieza de las gramticas con algoritmos con otras denominaciones, se adjunta a continuacin una tabla comparativa. Algoritmo
Reglas innecesarias Smbolos inaccesibles

jflap
Unit production removal Useless production removal (2 parte) Useless production removal (1 parte) Useless production removal (1 parte)

Teora dada en clase

Eliminacin de Reglas innecesarias Eliminacin de smbolos inaccesibles Eliminacin de reglas suprfluas

Diferencia
No hay

Comentarios
-----

No hay ----No hay ----En clase se proporciona un algoritmo distinto. Poner el presunto smbolo no generativo como axioma: si se obtiene lenguaje vaco, entonces es no generativo No hay El smbolo no generativo, si est en la parte derecha de una regla de gramtica G2, G3 puede eliminarse tratando esta regla como suprflua. ----No hay -----

Reglas suprfluas

Eliminacin de smbolos no generativos

Smbolos no generativos

Reglas no generativas Reglas de redenominacin

production removal Unit production removal

Eliminacin de reglas no generativas Eliminacin de Reglas de redenominacin

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

4.1 Eliminando reglas no generativas (Lambda removal)

La idea es identificar las producciones que deriven en , eliminarlas, y sustituirlas con producciones equivalentes. Una regla no generativa es A::= , siendo A un no terminal y A S. Si L(G) se aade S::= y A NT (A::= A S) y regla de la gramtica de la forma B::=xAy, aadiremos a la lista de las producciones una regla de la forma B::=xy, excepto en el caso de que z=y= .

Figura 11: Eliminacin de una produccin La transformacin Despus de introducir una gramtica con el editor, selecciona Convert > Transform Grammar. Aparecer una ventana como la de la Figura 11. La transformacin se realiza en dos pasos: El primero consiste en identificar el conjunto de producciones que derivan en . En el ejemplo son las producciones 3 y 5 de A y B, respectivamente. Pincha en cada una de las producciones de A (A aAa y A ), y lo mismo con B, para aadir A y B al conjunto de no terminales que derivan en , tal y como se muestra en el ejemplo, de la Figura 11. C puede derivar en ? No es algo obvio, como en el caso de A y B. Sin embargo, la parte derecha de C B es un elemento del conjunto de no terminales que derivan en , lo que implica que C tambin deriva en . Pincha en la produccin C B para aadirla al conjunto. Las producciones que slo tengan en la parte derecha elementos que pertenezcan al conjunto de no terminales que derivan en (como D AB), tambin se incluyen (haz clic sobre D para aadirlo del mismo modo). En este punto el conjunto se ha completado y JFLAP va al siguiente paso. El segundo paso es obtener una gramtica equivalente sin producciones . La gramtica original ahora aparece en la parte derecha de la ventana. Ahora tendremos que borrar las producciones , y aadir otras nuevas en esta parte de la ventana. Para cada produccin de la gramtica original que en la parte derecha tuviera un no terminal del conjunto que hemos obtenido antes (los que derivan en ), se tiene que agregar una nueva produccin sin ese smbolo, excepto si la nueva produccin deriva en . En el ejemplo, para A aAa aadimos A aa y en el caso de D AB, aadimos D A y D B. Una forma alternativa de aadir las producciones es seleccionando primero la produccin en la gramtica original de la izquierda y haciendo clic en Complete Selected. Otra forma ms rpida es pulsando el botn de Do Step o Do All.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

Cuando se complete el proceso aparecer un mensaje de aviso en la ventana. A partir de aqu, puedes pasar a la siguiente transformacin pulsando en Proceed, o puedes exportar primero la gramtica modificada a una nueva ventana pulsando Export. En cualquier caso, la gramtica modificada es equivalente a la original.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

10

4.2 Eliminando reglas de redenominacin (Unit removal)

Una regla de redenominacin es una regla del tipo A::=B. Estas producciones no aaden terminales en la derivacin, y no incrementan la longitud de la forma sentencial. Adems, pueden causar problemas si se crea un ciclo (A::=B y B::=A). Por lo tanto, hay que identificar estas reglas, eliminarlas y aadir otras que las reemplacen en una gramtica equivalente. Si hay alguna regla de este tipo, entonces A NT | A::=B en la gramtica y (B::=x) P donde x NT P = P + {A::=x}. Usaremos un grfico de dependencia de variables (VDG, donde los no terminales son nodos) para representar todas las reglas de redenominacin que hay y las direcciones de las producciones (si A B, entonces hay una flecha del nodo A al B).

Figura 12: Eliminacin de reglas de redenominacin La transformacin En este caso, probaremos con un ejemplo distinto al anterior. Para llegar a la ventana que se muestra en la Figura 12, se deben seguir los pasos explicados en 4.1. (en este caso, como no hay producciones , JFLAP se salta ese paso de la limpieza de gramticas). El primer paso es completar el VDG, que JFLAP crea a partir de la gramtica. El grfico representa las reglas de redenominacin como transiciones entre los nodos. Para cada regla (Ej: S A), se debe aadir una flecha entre los nodos etiquetados que correspondan (del S al nodo A). Los nodos se pueden mover usando el botn , y los enlaces se ponen con el botn , haciendo clic del nodo que representa la parte izquierda (S) y arrastrando hasta el que representa la derecha (A) (ver Figura 13). Una vez completo el grafo, pasamos al siguiente paso, que es borrar las reglas de redenominacin y aadir producciones equivalentes. Para la produccin A B de la gramtica original, aadiremos una produccin del tipo A w, por cada regla B w existente. En el caso de que w sea un nico smbolo no terminal, w pasa a ser el valor que tomar para las reglas X w. Para el caso del ejemplo, primero eliminaremos la produccin S A que es la nica con el axioma, seleccionando la regla, y pulsando en Delete. Aade las nuevas producciones segn la explicacin anterior y repite el proceso para los dems casos. Otra forma de hacerlo en pulsando en Complete Selected o utilizando Do Step o Do All.
Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

11

Figura 13: Eliminacin completa de reglas de redenominacin Cuando se haya terminado el proceso, podemos seguir con la transformacin de la gramtica pulsando en Proceed o exportar la nueva gramtica, equivalente a la anterior, pulsando en Export.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

12

4.3 Eliminacin de reglas superfluas y smbolos inaccesibles (Useless removal)

En este apartado eliminaremos las producciones que no contribuyen a la formacin de palabras x T*.

Figura 14: Ejemplo de eliminacin de reglas superfluas y smbolos inaccesibles, con el grafo de dependencia completo. La transformacin Si introducimos el ejemplo de la Figura 14, al ir a transformar la gramtica, JFLAP se saltar los dos primeros pasos que hemos visto anteriormente porque en este caso no son necesarios. El proceso tiene dos partes: La primera es encontrar los no terminales que no derivan en una cadena de terminales y eliminar las producciones con esos smbolos (reglas superfluas). Para ello, se realiza el proceso inverso, identificando las producciones tipo A a, que derivan slo en elementos terminales. Haz clic en esas producciones, para que se agreguen al conjunto de no terminales que derivan en terminales. Una vez hecho esto, hay que marcar los no terminales para los que existe una regla U::=x donde x * (x es una cadena de terminales, o contiene no terminales que ya se han marcado anteriormente). En el ejemplo, cuando hayamos marcado todos, veremos algo similar a la Figura 14. En la gramtica del recuadro inferior derecha de la ventana, vemos como las producciones que contenan el no terminal B han sido eliminadas, por ser superfluas. La segunda parte de la transformacin es encontrar los smbolos inaccesibles desde el axioma y eliminar las producciones con esos elementos. En el ejemplo, si aadimos las flechas de las producciones al grfico, vemos como no se puede acceder al elemento C desde el axioma. Por lo que esa regla se puede eliminar (seleccinala en el editor y pulsa en Delete). La gramtica queda tal y como se muestra en la Figura 15.
Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

13

La gramtica que tenemos ahora es equivalente a la anterior, ms pequea, una vez que se han eliminado las producciones que no eran necesarias. Llegado este punto, est preparada para pasarla a FNC.

Figura 15: Ejemplo con la transformacin completa 4.3

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

14

4.4 Convertir a Forma Normal de Chomsky.

La FNC es una forma restringida de una gramtica de contexto libre. En la FNC, la parte derecha de una produccin es o un elemento terminal, o dos elementos no terminales. De esta forma, el proceso de derivacin es ms rpido. La idea de esta conversin es reemplazar cada conjunto de terminales en la parte derecha de longitud superior a 1, por un no terminal. Entonces reemplazar cada par de no terminales adyacentes por otro no terminal, hasta que todas las partes derechas de las producciones con no terminales tengan exactamente dos no terminales. Pero primero todas las producciones , reglas de redenominacin y superfluas, que hubiera tienen que ser eliminadas, segn lo que hemos visto anteriormente. La transformacin Escribe en el editor de gramticas de JFLAP el ejemplo que se muestra en la Figura 16. Selecciona Convert > Transform Grammar, y aparecer una ventana como la de la figura.

Figura 16: Ejemplo de transformacin a FNC Primero convertiremos las producciones ms simples. Selecciona A Aa (la 2 produccin) de la tabla de la parte derecha. Esta produccin necesita ser reemplazada por dos producciones equivalentes que estn en FNC. Haz clic en Convert Selected, para modificarla. En este caso, B(a) es un nuevo no terminal representada por el terminal a, como una nueva produccin B(a) a. Ahora selecciona B bb y haz clic en Convert Selected. En este caso slo aparece una nueva variable B(b), con B B(b)B(b). Slo queda una produccin por convertir. Selecciona S ABAB. La parte derecha es muy larga, por lo que se necesitan pares de no terminales adyacentes para sustituir por variables nuevas, hasta que todas las producciones nuevas tengan la longitud correcta. En JFLAP esos no terminales nuevos sern D(n) donde n es un nmero que comienza en 1. Haz clic en Convert Selected para dividir esta produccin en dos: S AD(1) y D(1) BAB. Esta ltima regla necesita ser fragmentada en dos. Seleccinala y pulsa el botn anterior para dividirla en D(1) BD(2) y D(2) AB. Ahora todas las reglas tienen la forma adecuada, y la conversin se ha completado, como se puede ver en la Figura 17. En este punto, los no terminales de la forma B(x) y D(n) son temporalmente no terminales utilizados solo en el algoritmo de conversin. Cuando la gramtica sea exportada, sern reemplazados por letras en maysculas del abecedario que no se estuvieran usando ya. Si la gramtica reformada tiene ms de 26 no terminales, JFLAP no podr exportarla porque ser ms grande que el nmero de letras del abecedario ingls.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

15

Figura 17: Ejemplo completo de transformacin a FNC Ahora compara la gramtica en FNC con la original, ejecutando el brute-force parser con la palabra aaabbaabb para los dos casos. Cul de las dos ejecuciones es ms lenta? Qu rbol de derivacin ser ms pequeo?

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

16

5. Convertir una gramtica lineal derecha a un autmata finito

En esta seccin describiremos la conversin que puede hacer JFLAP de una gramtica lineal derecha a su equivalente autmata finito (AF). La gramtica y el autmata reconocern el mismo lenguaje regular. La idea detrs de esta transformacin es que los no terminales en una gramtica lineal derecha pueden funcionar de forma similar a los estados de un AF. Como ejemplo, considera la gramtica de la Figura 2 de este manual, y observa la derivacin con la palabra aqvx que aparece en la Figura 4 y 5. Empezamos la derivacin con el axioma, lo que se asemeja con el estado inicial del autmata. Cuando vamos a la produccin S aA, es similar a leer una a y movernos al estado A. El siguiente paso de la derivacin sera A B, lo que es parecido a transitar del estado A al B, sin leer nada, o dicho de otra forma, como si leyramos . Despus, la produccin B qvC es como si del estado B furamos al C, una vez ledo qv. Finalmente, la ltima produccin C x, es anloga a leer x, y pasar al estado final desde C, ya que no hay ms derivaciones. De forma genrica, con NT={A,B} y T={,} podemos decir que una produccin A B es como una transicin en el AF desde el estado A al B, leyendo . Y una produccin A es como una transicin del estado A, al estado final del autmata, leyendo .

Figura 18: Conversin finalizada a un AF. La Figura 18 muestra la conversin finalizada de la gramtica que hemos usado de ejemplo a un AF. Para ir al conversor, una vez cargada la gramtica a transformar, selecciona en el men Convert > Convert Right-Linear Grammar to FA. La ventana que aparecer ser similar a la de la figura, con los estados del autmata marcados con los smbolos no terminales equivalentes, exceptuando el estado final, que no tiene. La finalidad del conversor es crear las transiciones del AF segn cada una de las producciones de la gramtica a transformar. La primera produccin que convertiremos ser S aA. Crea una transicin del estado S al A con el terminal a, y cuando lo hagas vers como se marca el cuadrado de la columna Created, para indicar que ya se ha marcado la transicin. Realiza este mismo proceso con las dems producciones de la gramtica.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

17

JFLAP gestiona algunos errores que pueden aparecer en el conversor. Como prueba de ello, intenta introducir una transicin errnea, como mover del estado C al A, leyendo xyz. No existe ninguna produccin A xyzS, por lo que esta transicin no pertenece al AF. Cuando termines de editar la transicin, una ventana de aviso aparecer para decirte que esa transicin no est en la gramtica que estamos convirtiendo. Si pinchas en el botn Done, JFLAP te avisar en caso de que no se haya completado la conversin, especificando el nmero de transiciones que faltan por aadir, y resaltando en rojo las producciones concretas de la gramtica que falten por aplicar al AF. Una forma ms rpida de crear las producciones, es seleccionar la fila de la gramtica con la produccin y pinchar en el botn Create Selected. JFLAP crear la transicin correspondiente automticamente. Tambin se puede pulsar en Show All para completar toda la conversin. Cuando hayas terminado todo el proceso, pulsa el botn Export, y tu autmata finito determinista aparecer en una nueva ventana. Despus de exportarlo, puedes modificar el AF.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

18

6. Convertir un AF en una gramtica lineal derecha

Ahora veremos el proceso contrario a lo visto en el punto 5: pasar de AF a gramtica. La idea es la misma que antes, pero a la inversa: si en la conversin anterior una produccin AxyzB, era una transicin del estado A al B, con xyz; ahora, una transicin del estado A al B, leyendo xyz, se traduce en una produccin A xyzB. Al principio, la herramienta asignar a cada estado un no terminal, fijando el estado inicial como el axioma S. El caso de las producciones ya lo conocemos. Por ello, la parte donde hay que tener cuidado es en la conversin del estado final. En el punto 5, el estado final no corresponda a ningn elemento de la gramtica. Era el destino de las transiciones resultantes de las producciones que no tenan no terminales en la parte derecha, lo que implicaba el final de la palabra. Sin embargo, ahora es diferente: puede haber transiciones desde el estado final a otro estado cualquiera del autmata. Esto significa que en la conversin a la gramtica, un estado final deber corresponder a un no terminal mientras la expansin de la cadena sea posible. Por lo tanto, para cada estado final F, se deber incluir la produccin F .

Figura 19: Autmata finito inicial.

Figura 20: Ejemplo de conversin de un AF.

Para la conversin de un AF a una gramtica, desde la ventana de autmatas finitos, seleccionar Convert > Convert to Grammar. El mtodo es muy sencillo. Cada transicin y cada estado final corresponden a una produccin en la gramtica. Cuando selecciones una transicin o estado final, su produccin aparecer en la parte derecha de la ventana (ver Figuras 19 y 20). Pincha en cada transicin del esquema del autmata, y tambin en el estado final q4, lo que producir D . Al final, deber quedar algo similar a lo que aparece en la Figura 20. El botn Hint, mostrar una produccin para un elemento que no ha sido aadido an a la tabla de la derecha. Si seleccionas este botn, una produccin se aadir, y la parte correspondiente del esquema del AF se sombrear en color rojo. El botn Whats Left, remarcar los objetos que queden que an no se han convertido. Una forma de hacer la conversin de una vez para todo el autmata es pulsando en el botn Show All. Al final pulsa en el botn Export para obtener en una ventana a parte la nueva gramtica obtenida a partir del autmata.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

19

7. Autmatas Finitos
En este captulo construiremos un autmata determinista en JFLAP, ilustrando algunos mtodos de simulacin, etc... En las secciones 7.1-7.4, mostraremos la definicin estndar de AFD, y en la 7.5 veremos como JFLAP maneja una definicin ms general de un AFD con mltiples transiciones de caracteres.

7.1 Un autmata finito simple

Para empezar a construir un AF, pincha en el men de inicio de JFLAP en el botn Finite Automaton. Aparecer una ventana, con un men, una pestaa que es el Editor, una barra de herramientas y un rea en blanco que ocupar casi toda la ventana. 7.1.1 Crear estados Un autmata est formado por un conjunto de estados. Antes de crear uno, primero debes activar el botn , en la barra de herramientas. Mientras est seleccionado, el botn estar sombreado. La zona grande en blanco, llamada canvas, es donde construiremos el autmata. Ahora que la herramienta para crear estados est activada, pincha en el canvas para crear un estado. Aparecer en la zona donde hayas pinchado. JFLAP los identificar en el orden en el que se creen como q0, q1, q2... 7.1.2 Definir el estado inicial y el final Todos los autmatas requieren un estado inicial y un conjunto de estados finales. Para marcar q0 como el estado inicial, selecciona el botn y despus, con el botn derecho del ratn pincha en el estado q0. Aparecer un men sobre el estado del autmata (el resto de las opciones del men se explicarn en la seccin 7.1.5), en el que escogeremos Initial. Ahora el estado q0 queda marcado con una flecha que indica que es el inicial. Igualmente, realiza el mismo procedimiento con q3 pero seleccionando Final en el men. El estado q3 quedar con un doble crculo. Para modificar los estados iniciales/finales, se realiza el mismo procedimiento, volviendo a escoger Initial/Final en el men, para eliminar la marca de check que habamos puesto antes. 7.1.3 Creando transiciones En el ejemplo, hay 3 transiciones. Para crearlas, pincha en el botn . Una vez seleccionado, pincha en el estado q0, y sin soltar el botn, arrastra el cursor del ratn hacia el estado q1 y despus, sultalo. Un campo de texto aparecer entre los dos estados. Escribe una b y dale a intro. Una nueva transicin b del estado q0 a q1 apareci. De la misma forma, crea el resto de transiciones para que el autmata quede igual que el de la Figura 21. Para transiciones , deja el campo de texto en blanco.

Figura 21: Ejemplo del editor de autmatas finitos.

Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

20

Para los loops, simplemente pincha sobre el estado en el que quieras hacer el loop y suelta el ratn. Aparecer la ventana donde debers escribir el texto. Si quieres cancelar en algn momento una transicin, o una edicin, pulsa escape. 7.1.4 Borrando estados y transiciones Si te confundes y creas estados o transiciones de ms, borrarlos es muy sencillo. Selecciona el botn , y haz doble clic sobre el elemento que quieras eliminar. En el caso de las transiciones puedes pinchar en la misma flecha o en la etiqueta. En los estados, cuando se borra uno, se eliminarn automticamente todas las transiciones que entren o salgan del estado. Para no eliminar algo por error, selecciona el botn de nuevo, y as ya no estar activada la herramienta de borrado. 7.1.5 Herramienta de editor En el punto 7.1.2 ya se ha explicado alguna funcin para el botn , pero tiene otras muchas funciones relacionadas a la modificacin de los atributos de los estados existentes y de las transiciones: Marcar estados como inicial/final: esto ya lo hemos visto en la seccin 7.1.2 Mover estados y transiciones: pincha sobre el elemento que desees mover y arrstralo a la nueva localizacin. Si mueves una transicin, movers tambin los estados implicados. Editar transiciones existentes: haz clic sobre la transicin que quieras modificar, y cambia lo que haba antes en el campo de texto. Etiquetas: Si pinchas con el botn derecho del ratn sobre un estado, veras en el men Change Label. Al seleccionar esa opcin, aparecer una nueva ventana donde podrs escribir la nueva etiqueta. Estas etiquetas ayudan a identificar el significado del estado. En el ejemplo de la Figura 21, cuando estemos en q2, ser cuando llegue al autmata un nmero par de bs. En q1 tendremos un nmero impar. Por ello, podramos etiquetar q2 con n par de bs y q1 con n impar de bs. Para borrar una etiqueta existente, haz clic en Clear Label, y para borrar todas las que haya, pincha en Clear All Labels. Si pinchas con el botn derecho, en una zona en blanco, aparecer un men diferente con la opcin Display State Labels. Esta opcin est activada por defecto. Si la desactivas, las etiquetas sern invisibles. Las podrs ver, posicionando el cursor del ratn durante un par de segundos sobre un estado en el que hubieras aadido previamente una etiqueta. Disposicin automtica: pulsa el botn derecho en una zona en blanco. Observa que hay un elemento en el men, que pone Layout Graph. Cuando est seleccionado, JFLAp aplicar un algoritmo de ordenacin grfico sobre el autmata. Esta opcin es til sobre todo, cuando hay un gran nmero de estados y transiciones, ya que JFLAP los colocar para que el autmata se vea de la forma ms sencilla posible, ahorrndonos el proceso, a veces tedioso, de ir moviendo cada elemento por separado. Nota: Existen comandos para ejecutar algunas de estas opciones ms rpido. Por ejemplo, manteniendo el cursor del ratn sobre el icono de la herramienta de creacin de estados, aparecer (S)tate Creator. El parntesis que encierra a la S indica que esa es la tecla rpida para crear estados. Pulsando la letra correspondiente (en minsculas), activaremos la opcin deseada sin necesidad de usar el ratn.
Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

21

7.2 Simulacin de una entrada en el autmata

En esta seccin estudiaremos tres de los mtodos de JFLAP para simular el resultado de una entrada en un autmata: simulacin por pasos, simulacin rpida y simulacin mltiple. El cuarto tipo stepping by state se ver brevemente en 7.3. 7.2.1 Simulacin por pasos (Stepping simulation or Stepping with closure) La simulacin por pasos te permite ver cada configuracin generada por un autmata al procesar una entrada. La siguiente figura muestra un ejemplo de una simulacin por pasos de la entrada aabbb en el autmata de la Figura 21. Para seleccionar esta herramienta, ve a Input > Stepping with closure. Te aparecer una ventana, donde tendrs que introducir la entrada del autmata.

Figura 22: Inicio de la simulacin por pasos con la entrada aabbb. En la Figura 22 vemos como el estado activo del AF est sombreado. La zona por debajo del dibujo del AF muestra la configuracin actual. Comenzamos en el estado inicial q0, y al pulsar Step las letras de la palabra de entrada se irn sombreando, a la vez que cambiar el estado actual, segn sea la entrada recibida en cada caso. Si la palabra es aceptada, el dibujo con la configuracin actual tendr un fondo verde. Si no es aceptada por el AF, el fondo ser rojo. Algunas de las operaciones de la barra de herramientas que se encuentra en la parte baja de la ventana (Figura 22) solo funcionan cuando hay una configuracin seleccionada. Para seleccionarla, pincha en ella. Puedes ver como al hacerlo, el color se oscurece un poco. Si pinchas ahora en Remove, eliminars la configuracin actual. Para empezar de nuevo con la simulacin, pincha en Reset. Para ver todos los pasos anteriores que se han dado para llegar a una configuracin, seleccinala y despus pincha en Trace. Se abrir una nueva ventana con todo el proceso desde la configuracin inicial, arriba del todo, a la actual. 7.2.2 Simulacin rpida (Fast Simulation) Esta simulacin permite ver rpidamente si el autmata acepta o no una entrada. Si la acepta, aparecer la lista con los pasos dados hasta llegar al final (similar a obtener la traza en el punto anterior). En caso contrario, aparecer un mensaje para informar. Selecciona Input > Fast Run. Escribe aabbb como entrada al autmata y el resultado que te dar JFLAP ser como el de la Figura 23. Observa los dos botones de la ventana. Im Done cerrar la ventana. Keep Looking ser til para autmatas no deterministas y eso lo veremos en la seccin 7.3.2.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

22

Figura 23: Resultado de una simulacin rpida. 7.2.3 Simulacin mltiple Este mtodo permite realizar funcionamientos mltiples de una vez, rpidamente. Selecciona Input > Multiple Run. Aparecer una ventana similar a lo que se muestra en la Figura 24.

Figura 24: Ejemplo de simulacin mltiple. En la fila 7 de inputs se introdujo lambda. El procedimiento es similar al del derivador mltiple por fuerza bruta que utilizamos en gramticas. Escribe las entradas que quieras probar en la columna de inputs, como se muestra en el ejemplo, y pulsa en Run Inputs. La columna de la derecha mostrar los resultados obtenidos. La lista de inputs que introduzcas, JFLAP los recordar la prxima vez que abras la simulacin mltiple, mientras no reinicies el programa.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

23

7.3 No determinismo
En esta seccin trataremos los autmatas finitos no deterministas (AFND) en JFLAP, utilizando el autmata que se muestra en la Figura 25 como ejemplo.

Figura 25: AFND que acepta el lenguaje anbm, con n>0, m 0, y n,m divisibles por dos y por tres. Hay dos condiciones que implican que un AF sea no determinista. La primera condicin es que el AF tenga dos transiciones del mismo estado que tengan el mismo smbolo de entrada (en la figura q1 tiene dos transiciones que leen a). La segunda es que alguna transicin lea . 7.3.1 Crear un autmata no determinista El proceso es bsicamente el mismo que para un autmata determinista. La mayor diferencia es la existencia de transiciones . Para crear una de ellas, solo tienes que crear una transicin normal, pero dejando el campo de texto en blanco. Ahora fjate en la Figura 25, y en un editor nuevo de autmatas haz el mismo esquema. Recuerda que los estados se numeran segn los vayas creando, as que ten cuidado en que estn colocados en el mismo orden. 7.3.2 Simulacin Durante la simulacin, una entrada en una mquina determinista produce un solo camino de configuraciones, mientras que en una mquina no determinista, los caminos son mltiples. Los simuladores de JFLAP diferencian ambos casos: Simulacin por pasos, (Step with Closure): Selecciona Input > Step with Closure e introduce la palabra aaaabb. Despus de esto, vers el familiar simulador por pasos, con una configuracin inicial en q0, con toda la palabra esperando por ser procesada. Pulsa Step una vez para mover a q1. Sin embargo, si pulsas una segunda vez, vers como la forma del simulador cambia, como se muestra la Figura 26. Hay 4 configuraciones en el simulador porque es un AFND: la ltima configuracin estaba en q1, y faltaba por leer aaabb, y q1 tiene transiciones a al estado q2 y q9. Pero al estar conectados esos estados con transiciones , la simulacin por pasos no solo conecta con qi, sino tambin con aquellos que leen la palabra vaca desde qi. El conjunto de estados alcanzables desde qi con transiciones , es llamado closure (encierro) de qi.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

24

Figura 26: Simulacin de aaaabb despus de dos pasos en el AFND. De estos caminos de configuraciones, el de q9 es el que puedes ver que nos llevar a la aceptacin de la palabra. Selecciona esa configuracin, y pincha en Freeze. El recuadro se colorear de un azul ms oscuro. Ahora pulsa en Step de nuevo: mientras que las dems configuraciones se mueven (y son rechazadas), esta configuracin no progresa porque la hemos congelado. Ahora pulsa Thaw, con esa configuracin seleccionada. Esto la descongelar, y al pulsar en Step, podremos continuar con ese camino hasta ver como es aceptada. Pincha en la configuracin aceptada y pulsa en Trace. Observa como hay un camino directo de q10 a q11, aunque no hay transicin de q10 a q11. No se ha generado ninguna transicin para q9 por la transicin que hay. Simulacin por pasos (Step by State): Selecciona en el men Input > Step by State, e introduce la palabra aaaabb. En esta simulacin la herramienta pasa explcitamente por las transiciones . Si pulsas en Step dos veces, tendrs las configuraciones en q2 y q9, pero no las configuraciones en q6 y q11, que vimos antes. Si pulsas de nuevo, la configuracin en q9 se dividir en tres ms, dos de las cuales son q6 y q11. Si continuas avanzando en la simulacin hasta la aceptacin de la palabra, y muestras la traza, la configuracin despus de q10 es q9, lo cual deriva en q11 con la transicin . Aunque esta simulacin es menos confusa que la anterior, suele usarse menos esta, porque no garantiza que en cada paso se lea un smbolo de entrada. Simulacin rpida: El simulador rpido tiene algunas caractersticas adicionales especficas para el no determinismo. Selecciona Input > Fast Run, e introduce la palabra aaaaaabb. Una vez hecho esto JFLAP mostrar una de las trazas de aceptacin de la palabra. El botn Keep Looking es til para mquinas no deterministas, ya que sirve para visualizar la traza del resto de caminos distintos que hay para llegar a aceptar la palabra. Si pulsas ese botn una vez, comprobars como JFLAP muestra otro caso distinto. Y si pulsas de nuevo, aparecer un mensaje que te dir que ha habido dos configuraciones (dos trazas) aceptadas, y que no hay ms configuraciones posibles. Simulacin mltiple: La simulacin multiple solo presenta una traza por ejecucin. Especficamente, cuando se acepta una palabra, JFLAP mostrar la traza de la primera configuracin aceptada, y cuando se rechaza, se mostrar la traza de la ltima configuracin rechazada. Por lo que si quieres depurar un AFND es mejor utilizar alguna de las otras simulaciones. 25

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

7.4 Operadores simples del anlisis

Adems de las simulaciones, JFLAP ofrece algunas herramientas para determinar algunas propiedades del autmata. 7.4.1 Comparar equivalencias Este operador compara si dos autmatas aceptan el mismo lenguaje. Para ilustrar el funcionamiento, de esta herramienta, compararemos el autmata de la Figura 20, y el de la 27.

Figura 27: ejemplo de un autmata finito que reconoce el mismo lenguaje que el autmata de la figura 20. Para comparar dos autmatas, debes tener una ventana de editor abierta para cada uno de los autmatas que vayas a comparar. Despus, en una de esas ventanas, en a barra de herramientas ve a Test > Compare Equivalente. Aparecer una ventana emergente con una lista donde podrs elegir el nombre del autmata con el que quieres comparar el autmata del editor actual. Una vez seleccionado, pincha en OK, y aparecer una ventana informando de que son equivalentes. En el caso de que los autmatas no lo sean (prueba a cambiar algo en uno de los dos autmatas y a compararlos de nuevo), recibiremos el aviso de que no aceptan el mismo lenguaje. 7.4.2 Marcar no determinismo Este operador mostrar al usuario que estados en el autmata son no deterministas. En el ejemplo de la Figura 25, el estado q1 es obviamente no determinista y adems de ese tipo de estados con dos salidas diferentes para una misma entrada, JFLAP considera a todos los estados con transiciones salientes como no deterministas, por lo que q3 y q9 tambin lo son. Selecciona Test > Highlight Nondeterminism, para marcar esos estados. 7.4.3 Marcar transiciones Este operador mostrar de rojo todas las transiciones . Selecciona Test > Highlight .Transitions para marcarlas.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

26

7.5 Transiciones alternativas de mltiples caracteres.

JFLAP proporciona una definicin ms general de un AF, permitiendo mltiples caracteres en una transicin. Esto puede resultar en AFs simples. En la Figura 28 hay un AFND de 5 estados que acepta el mismo lenguaje que el AFND de la Figura 25. Observa que en la Figura 28 las transiciones que no tienen mltiples smbolos son transiciones . Una configuracin puede ir a una transicin de n caracteres s1s2sn, si los prximos smbolos de entrada son s1, s2, hasta sn.

Figura 28: Ejemplo de AFND con mltiples caracteres en las transiciones Ahora ejecutaremos una simulacin de este AFND. Selecciona Step With Closure, e introduce aaaabb. Aparecer la ventana del simulador con la configuracin iniciada en q0. Pincha una vez en Step, y vers seis configuraciones. Hay dos por q3 y q4, una por q1 y otra por q2. Observa que esas dos configuraciones tienen una cantidad diferente de elementos que an no se han ledo. Da dos pasos ms y aparecer un estado de aceptacin en q3 (figura 29) Al permitir mltiples caracteres en las transiciones, la primera condicin para un AFND de la seccin 7.3 cambia. La primera condicin esa ahora la que sigue: si un AF tiene dos transiciones desde el mismo estado que leen la palabra A y B, donde A es un prefijo de B, el AF es considerado AFND. Por ejemplo, en la Figura 28, q0 es un estado no determinista: tiene dos transiciones, una con aaa y otra con aa, por lo que es un AFND.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

27

7.6 Definicin de AF en JFLAP

JFLAP define un AF M como la quntupla M = (Q, , , qs, F) donde: Q es un conjunto finito de estados {qi | i Z} es el alfabeto finito de entrada. es la funcin de transicin, : D 2Q donde D es un subconjunto finito de Q x *. qs Q es el estado inicial. F c Q es el conjunto de los estados finales. Hay unas variaciones respecto a la funcin de transicin: si es un AFD : Q x Q, y si es un AFND es la funcin de transicin : Q U {} 2Q. Para el caso de las transiciones con mltiples caracteres, la definicin del dominio de cambia: el conjunto Q x * es de infinita cardinalidad, aunque la funcin de transicin requiere un dominio finito. * simboliza una palabra de 0 o ms smbolos del alfabeto de entrada.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

28

8. AFND a AFD y a AFD mnimo

Este capitulo muestra como un AFND puede ser convertido en su equivalente AFD y como cada AFD puede ser reducido a un AFD con el nmero mnimo de estados. Aunque un AFND puede ser ms fcil de construir que un AFD, es menos eficiente en la ejecucin.

8.1 AFND a AFD

La idea es crear estados en el AFD que representen mltiples estados de un AFND. El estado inicial en el AFD representa el estado inicial en el AFND y cualquier estado accesible desde el con . Para cada nuevo estado en el AFD y para cada letra del alfabeto, uno determina todos los estados accesibles desde el correspondiente estado no determinista y los combina en un nuevo estado para el AFD. Este estado ene. AFD tendraa una etiqueta que contendr los nmeros de los estados del AFND que podrn ser accedidos tomando el mismo camino. 8.1.1 Idea para la conversin Primero vamos a examinar las opciones que hay cuando se procesa una palabra en un AFND, con el ejemplo que se muestra a continuacin:

Figura 29: Ejemplo de AFND Selecciona Input > Step with Closure e introduce aabbbaa. Si vas pinchando en Step, vers como de inicio podemos ir a q0 y q1, y que hay siempre 3 configuraciones (una de ellas, de rechazo). Los estados en el AFD construido representaran la combinacin de estados del AFND. Por ejemplo, procesando una a resulta el estado q0 o el q1. El AFD podr tener un estado que represente a ambos. Procesando aabbbaa llegamos al estado q2 y q3. El AFD podr tener un estado que represente a esos dos. 8.1.2 Ejemplo de conversin Ahora vamos a convertir el AFND de la figura 29 a un AFD (pincha en Convert > Convert to DFA). El estado inicial en el AFD es q0 y tiene la etiqueta 0, lo que representa el estado q0 del AFND. Despus de esto podemos aadir el estado que se alcanza desde q0 leyendo a. Selecciona el Expand Group, de la herramienta . Pincha y mantiene pulsado el botn del ratn en el estado q0, y arrastra el cursor hacia donde quieras colocar el siguiente estado y sultalo. Aparecer una ventana preguntando el terminal con el que vamos a expandir, que ser el smbolo a. Al introducir esto, JFLAP nos preguntar por el grupo de estados del AFND que son accesibles desde q0 al introducir una a, que sern q0 y q1 (estos estados estn representados por los nmeros 0 y 1, que es lo que habr que

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

29

introducir en la ventana). Una vez hecho todo esto, un nuevo estado q1 aparecer, tal y como se muestra en la figura 30.

Figura 30: Ejemplo de expansin del estado q0 con la entrada a. Intenta expandir el estado q0 del AFD, con el terminal b. Como no hay ningn camino desde el AFND con esas caractersticas, un mensaje de aviso aparecer. Ahora expande el estado q1 del AFD con el terminal a. Date cuenta que ese estado representa los estados q0 y q1 del AFND. En el AFND, el estado q0 al leer a, transita a q0 y a q1, y el estado q1 no transita a ningn otro estado. La unin de esos resultados (0,1) ser el q1 del AFD. Para ello, expande el estado q1 aadiendo un loop. Despus de eso, expandelo de nuevo en el estado q1 con b. El resultado de esatas expansiones se muestra en la figura 31. El estado q2 del AFD estar marcado como un estado final, porque los estados equivalentes en el AFND son finales tambin.

Figura 31: Expansin de a, b desde q1 Figura 32: Expansin de a, b desde q2. Expande ahora el estado q2 del AFD con a. Este estado est representado por los estados q1 y q2 del AFND, en los que q1 no tiene transiciones a, y q2 si la tiene. Expande el estado q2 del AFD con b, pinchando en el estado q2. El AFD resultante es el de la figura 32. Hay otra forma de expandir un estado, y es utilizando la herramienta . Cuando se selecciona esta herramienta y se pincha en un estado, y todos los arcos que tuvieran que salir de ese estado aparecen automticamente. Prueba a realizar esto en q3. Est el autmata completo? Pulsando en el botn Done? JFLAP nos avisar sobre los elementos que aun falten, o nos dir si ya lo hemos completado. En nuestro caso, aun falta una transicin, del estado q4 nuevo que ha aparecido. Utiliza la herramienta anterior para completarlo, y el autmata resultante deber ser como el de la figura 33.

Figura 33: El autmata finito determinista completo.

Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

30

Ahora vuelve a pulsar el botn Done?. El AFD completo es exportado a una nueva ventana. De forma alternativa, el botn Complete puede ser seleccionado en cualquier momento del proceso de construccin y el AFD se completar automticamente. El nuevo AFD debe ser equivalente al AFND. Para probar esto, selecciona en la barra de herramientas Test > Compare Equivalence.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

31

8.2 Conversin al AFD mnimo

En esta seccin mostraremos como convertir un AFD a un autmata equivalente con un nmero mnimo de estados. Esto viene de considerar dos estados p y q de un AFD, que procesan un smbolo desde su estado. Si hay al menos una palabra w para la cual los estados p y q la procesan, y un estado acepta w y otro rechaza w, entonces esos estados son distinguibles y no pueden ser combinados. Por otra partes, si los estados p y q actan del mismo modo, significa que son indistinguibles, y pueden ser combinados. 8.2.1 La idea de la conversin Utilizaremos el AFD de la siguiente figura de ejemplo, para explicar el proceso.

Figura 34: AFD de ejemplo para el punto 8.2. Una forma de ir viendo los estados distinguibles y los que no, es abriendo dos ventanas distintas de JFLAP, con el mismo ejemplo. Para ello, cralo en el editor, gurdalo dos veces con distintos nombres, y podrs verlos en dos ventanas. Ahora pasaremos a examinar los estados q0 y q1, para ver si son distinguibles. En una de las dos ventanas, cambia el estado inicial por q1. Examina los dos AFD. Hay alguna palabra que un AFD acepte y el otro rechace? Vamos a explorar varias entradas para ver si hay alguna diferencia. En las dos ventanas, selecciona Input > Multiple Run, e introduce estas entradas y otras que se te ocurran: a, aab, aaaab, baa, baaa y bba. Pulsa Run Inputs y examina los resultados. Son los mismos resultados? Hay por lo menos una palabra en la que el resultado es Accept para un AFD y Reject en el otro. Por tanto, esos dos estados son distinguibles y no se pueden combinar. Ahora vamos a examinar los estados q2 y q5. En una de las ventanas del editor de los dos AFD cambia el estado inicial por q2, y en la otra por q5. Selecciona Input > Multiple Run de nuevo. Las entradas de la ltima ejecucin an aparecen en la ventana, as que pulsa en Run Inputs para probarlas. Aade otras palabras y prubalas tambin. Son distinguibles? Para determinar que dos estados son indistinguibles, se deben probar todas las posibles entradas, pero como esto no es posible, un conjunto razonable de test que nos creemos servir.

Grado en Ingeniera Informtica

Teora de Autmatas y Lenguajes Formales

32

8.2.2 Ejemplo de conversin. Abre el archivo donde tuvieras guardado el autmata de la Figura 34 y selecciona Convert > Minimize DFA. La ventana se separar en dos mostrando el AFD a la izquierda y un rbol de estados en la derecha. Se asume al principio que todos los estados son indistinguibles. La raz del rbol contiene todos los estados. Cada vez que determinemos una distincin entre estados, aadiremos un nodo en el rbol para mostrarla. Se continuar dividiendo nodos hasta que no haya ms divisiones posibles. Cada hoja del rbol final representar un grupo de estados indistinguibles. El primer paso que JFLAP mostrar al abrirse la ventana, ser para distinguir los estados finales y los no finales. Por ello, el rbol se divide en el conjunto de estados finales y en los no finales, tal y como muestra la Figura 35.

Figura 35: Divisin inicial de estados del conversor. Para futuras divisiones, se seleccionar un terminal que distinga los estados en el nodo. Si alguno de los estados en un nodo hoja, para ese terminal, va a algn estado de otro nodo hoja, y otros estados con el mismo terminal van a estados que estn en otro nodo hoja, entonces el nodo deber ser dividido en dos grupos de estados. Vamos a explorar primero el nodo hoja con los estados no finales. Qu ocurre para cada uno de esos estados si procesamos una b? El estado q0 transita al q2, el q1 va al q0, y as sucesivamente. Cada uno de esos estados van a un mismo estado de esse nodo. Por lo tanto, la entrada b no los distingue. Si tratas de introducir b, en Set Terminal, JFLAP mostrar un mensaje informando sobre lo que ya habamos averiguado (para poder seleccionar esa herramienta, debes pulsar primero en el nodo del rbol correspondiente). Selecciona de nuevo Set Terminal e introduce el terminal a. En este caso, si que distingue los estados, por lo que el nodo se divide. El conjunto de estados que van en cada divisin debe ser introducido, en grupos que son indistinguibles. Un nmero de estado puede ser introducido seleccionando primero el nodo hoja donde estaba asignado, y entonces pinchando en el correspondiente estado en el AFD. Pincha en la hoja izquierda del nodo y entonces pincha en el estado q0 del AFD. El estado nmero 0 deber aparecer en el nodo hoja, tal y como se muestra en la Figura 36.

Figura 36: Divisin del nodo con a.

Grado en Ingeniera Informtica

Figura 37: Divisin completa del nodo(0,1,2,4,5,7).

Teora de Autmatas y Lenguajes Formales

33

Aade el resto de estados, a los nodos hojas, igual que has hecho con el estado q0, hasta llegar a la imagen mostrada en la Figura 37. Para ver si esta bien hecho, pincha en Check Node. Ahora debemos continuar con el resto. Probaremos con el nodo hoja con estados 0, 1, 4 y, 7, con a. Selecciona Set Terminal e introduce a. El estado q0 transita a q5 con a, el cual est en otro nodo hoja, y los estados q1, q4 y q7 realizan transiciones entre ellos, por lo que se mantienen en el mismo nodo. As que ya tenemos los grupos a dividir. Para ello, selecciona Auto partition y los estados se insertarn de forma automtica como aparece en la Figura 38.

Figura 38: rbol completo de estados distinguibles.

Figura 39: Estados para el AFD mnimo.

Cuando el rbol se haya completado, la nica opcin visible ser Finish. Selecciona ese botn, y la parte derecha de la ventana ser reemplazada por los nuevos estados del AFD mnimo. Hay un estado para cada nodo hoja del rbol (observa como las etiquetas de esos estados son las mismas que las del rbol son las mismas etiquetas). Ahora aade los arcos que faltan en el nuevo AFD utilizando la herramienta Transition Creator. En el AFD original hay una a desde el estado q0 al q5, por lo que en el AFD nuevo, deber existir una transicin que corresponda a esa, desde el estado q1 (que representa al antiguo estado q0), al q2 (representando al antiguo q5). Seleccionando Hint, JFLAP aadir una transicin por ti, y seleccionando Complete, se completar automticamente el autmata. Selecciona Done? para exportar el nuevo AFD a una ventana del editor. El AFD de estados mnimos debe de ser equivalente al AFD original. Prubalo utilizando Test > Compare Equivalence.

Figura 40: El AFD mnimo. Nota: cuando vas a dividir un nodo con la herramienta Set Terminal, aparecen dos hijos, pero es posible que el nodo a dividir pueda necesitar ms hijos. Si es as, es que puede haber 3 o ms grupos distinguibles a dividir con un terminal. En ese caso, tu puedes aadir los nodos hojas adicionales seleccionando el botn Add Child para cada hijo adicional deseado.
Grado en Ingeniera Informtica Teora de Autmatas y Lenguajes Formales

34