ToTalf: Tutorial online para Teoría de Autómatas y Lenguajes

Formales *

Román Sosa, Francisco de SandeDpto. de Estadística, I.O. y Computación

Universidad de La Laguna38271 La Laguna

e-mail: {alu1970,sande}@etsii.ull.es

Resumen

El Tutorial Online para Teoría de Autómatas yLenguajes Formales (ToTalf ) ha sido diseñadocomo una herramienta de apoyo a la realiza-ción de prácticas en la asignatura de Teoría deAutómatas y Lenguajes Formales. En los pla-nes de estudios de la Universidad de La La-guna, esta asignatura aparece con una fuertecomponente práctica (la mitad de sus crédi-tos) de modo que las prácticas de laboratorioconstituyen una parte esencial de la misma.

ToTalf permite a los alumnos experimentarcon los conceptos estudiados en las clases deteoría, a través de la ejecución de distintos al-goritmos que se aplican sobre los diferentes ti-pos de modelos de cómputo que se estudian enlas clases teóricas. La herramienta ha sido de-sarrollada en Java, y está disponible tanto enforma de aplicación como de applet, de modoque los alumnos pueden instalarla localmenteen sus ordenadores o bien utilizarla a travésde cualquier navegador. Dispone de un siste-ma de ayuda que facilita el uso de la interfazde usuario y para cada uno de los diferentesmodelos de cómputo contemplados se ofrecenal usuario ejemplos prede�nidos que se puedencargar directamente y que también ilustran elmodo de operación de la herramienta.

Uno de los objetivos esenciales en el diseñode la herramienta ha sido que ésta fuera unaaplicación abierta de modo que en el futuro seamuy fácil incorporar nuevas funcionalidades,

*El proyecto ToTalf ha sido �nanciado por el Vi-cerrectorado de Calidad Docente y Nuevos Estudiosde la Universidad de La Laguna en la II Convocatoriade Proyectos de Innovación Docente

ejemplos o completar y/o modi�car el sistemade ayuda.

1. Introducción

El proyecto ToTalf [11] es un sistema de ayu-da para el aprendizaje de conceptos básicos enla materia de autómatas y lenguajes formales.Concretamente, ha sido desarrollado para losalumnos que cursan la asignatura de Teoríade Autómatas y Lenguajes Formales (TALF)[5] en la Universidad de La Laguna, aunquealgunas de sus capacidades son también apro-vechables en la asignatura de Compiladores. Eldesarrollo del proyecto ha tenido una duraciónaproximada de seis meses y el primer prototipoha sido implantado a lo largo del curso acadé-mico 2003-2004.ToTalf aborda el estudio de la asignatura

mediante un enfoque práctico, dividiendo eltemario de la asignatura en cuatro módulosprincipales.

1. Autómatas �nitos y expresiones regulares

2. Gramáticas independientes del contexto

3. Máquinas de Turing

4. Autómatas a pila

En cada uno de los módulos, el usuario puedeintroducir un ejemplo del concepto correspon-diente, y aplicarle los distintos algoritmos quese encuentran implementados, y que se impar-ten en la asignatura. De esta forma, el alumnopuede aplicar directamente los conocimientosy algoritmos estudiados en las clases de teoría,en vez de tener que resolver cualquier proble-ma usando lápiz y papel, lo que en muchos

220 Fundamentos teóricos de la informática

casos conlleva demasiado tiempo, es propensoa los errores, y sumamente tedioso.En la actualidad es posible encontrar herra-

mientas de características similares a las deToTalf. Es el gran auge de Internet quien hapermitido la proliferación de programas de es-te tipo. Cada uno suele tener alguna propiedadinteresante, pero la carencia de otras los ha-cen ser herramientas de�cientes para nuestrospropósitos. En general, la mayoría se centra enun único aspecto: la simulación de autómatas�nitos. En el caso de las aplicaciones desarro-lladas fuera de España, el hecho de que todoslos menús así como el sistema de ayuda esté eninglés, desanima a algunos alumnos a utilizar-las. Revisemos a continuación las aplicacionesmás relevantes:

• JFLAP [2] es un paquete de herramientasgrá�cas diseñado como asistente en la en-señanza de conceptos básicos en TALF.Se trata posiblemente de la herramientamás so�sticada y evolucionada de este ti-po. Con respecto a ToTalf, la caracterís-tica más notable es que dispone de unainterfaz grá�ca a través de la cual el usua-rio puede introducir autómatas así comovisualizar grá�camente la salida de los di-ferentes algoritmos. La versión actual in-corpora diferentes mejoras que han sidoañadidas a las sucesivas versiones de esteconocido paquete.

• ABCEZ (Applet Based ComputabilityEnlightenment Zone) [3] es otra de las he-rramientas basadas en applets con mayorimpacto visual. Igual que JFLAP tambiénposee una cuidada interfaz grá�ca, peroen este caso centra su atención exclusiva-mente en la simulación de autómatas �ni-tos. Una de las características más desta-cables de este programa es su sistema deayudas.

• El applet diseñado por J. Calera [4] pa-ra la asignatura Lenguajes, Gramáticas yAutómatas en la Universidad de Alicantees uno de los pocos ejemplos disponiblesde herramientas similares a ToTalf en elcontexto español. Se centra también en al-goritmos orientados a autómatas �nitos, yal igual que en nuestro trabajo, en lugar

de invertir esfuerzo en el diseño de una in-terfaz grá�ca avanzada, se ha optado porimplementar un amplio conjunto de algo-ritmos.

• También mencionamos [8], [9] y [10], tra-bajos sobre simulación en autómatas �ni-tos, y que no aportan grandes diferenciasrespecto a los ya comentados en los pun-tos anteriores.

2. Contexto y Objetivos

En la Escuela Técnica Superior de Ingenie-ría Informática (ETSII) de la Universidad deLa Laguna se imparten los estudios correspon-dientes a las Ingenierías Técnicas en Informá-tica de Sistemas y de Gestión, así como los deIngeniero en Informática.

La asignatura de TALF �gura como tron-cal para las dos Ingenierías Técnicas, y tieneasignados un total de nueve créditos, reparti-dos en partes iguales entre teoría y prácticas.La asignatura se imparte a lo largo del primercuatrimestre del segundo curso.

TALF es una asignatura con unos conteni-dos eminentemente abstractos que se han de-sarrollado históricamente a partir de los pro-blemas concretos a los que se ha ido enfren-tando la comunidad cientí�ca en su intento deutilizar lenguajes de alto nivel en la programa-ción de ordenadores, de traducir automática-mente o de matematizar el lenguaje humanopara procesarlo automáticamente.

La repercusión más directa de los conteni-dos de TALF, quizás se produce en las asig-naturas del plan de estudios relacionadas concompiladores: Compiladores en las ingenieríastécnicas, así como Procesadores de Lenguajesen la Ingeniería en Informática. Aparte de estarepercusión directa, los contenidos de TALFtambién son fundamentales en muchos otroscampos y asignaturas estudiados en la carre-ra.

2.1. Objetivos generales de TALF

Con esta asignatura se pretende transmitir alalumno los conceptos fundamentales de la Teo-ría de Autómatas y Lenguajes Formales, pre-

X Jornadas de Enseñanza Universitaria de la Informática 221

sentándole una visión global de la misma yprofundizando principalmente en los aspectosmás aplicados como son las herramientas bá-sicas que se utilizan en el diseño de analizado-res léxicos y sintácticos a partir de expresio-nes regulares y gramáticas independientes delcontexto, respectivamente. Los objetivos prin-cipales de la asignatura son:

• Presentar los distintos métodos formalesde representación de lenguajes, estudian-do métodos generativos (gramáticas) ymétodos por aceptación (autómatas).

• Conocer las herramientas que se utilizanpara describir, reconocer y caracterizardichos lenguajes.

• Desarrollar la capacidad de abstracción yanálisis teórico en relación con la teoríade lenguajes.

2.2. El programa de teoría

El temario de teoría impartido en la asignaturaes el siguiente:

1. Introducción al lenguaje C++.

2. Conceptos básicos

3. Lenguajes regulares y autómatas �nitos.

4. Gramáticas. Lenguajes independientesdel contexto. Autómatas a pila.

5. Máquinas de Turing. Lenguajes recursivosy recursivamente enumerables.

6. Resolubilidad.

2.3. El programa de prácticas

Sin desdeñar los contenidos teóricos, indispen-sables para el desarrollo de cualquier técnica,consideramos que los estudios de Informáticason eminentemente prácticos y es por ello queen las asignaturas que impartimos, las prácti-cas con ordenador constituyen un aspecto fun-damental de las mismas como complementoinsustituible a las clases de teoría. Semanal-mente los alumnos presentan en una sesión decorrección de prácticas una de las prácticas cu-yo enunciado se les ha propuesto con antela-ción. Los contenidos de las diferentes prácticaspueden variar de un año a otro, pero como esnatural, siempre están íntimamente relaciona-das con los temas que se estudian en teoría.

Los objetivos docentes a alcanzar a travésde las prácticas de la asignatura los podemosresumir en:

1. Introducir a los estudiantes en un lengua-je de programación orientado a objetos,que es nuevo para ellos (durante el pri-mer curso de la carrera los alumnos desa-rrollan sus prácticas usando Pascal).

2. La consolidación a través de las experien-cias de laboratorio de los conceptos ad-quiridos en las clases teóricas.

3. Mejorar el dominio de la programaciónadquirido en el curso anterior en las asig-naturas de Metodología y Tecnología de laProgramación I y II.

2.4. Objetivos del Proyecto ToTalf

El proyecto ToTalf surge como una necesidaddel profesor para mejorar la enseñanza de laasignatura. Para este �n, ToTalf implementala totalidad de los algoritmos que se progra-man en las prácticas (hay que tener en cuentaque las prácticas de la asignatura cambian encada uno de los cursos), y muchos otros al-goritmos interesantes estudiados en las clasesde teoría, incluyendo algunos correspondien-tes a la asignatura de Compiladores. Entre losobjetivos que perseguía ToTalf en su plantea-miento inicial, cabe destacar los siguientes:

• Como ya se comentó en la introducción,trata de ser una herramienta para ayudaral alumno en la comprensión de la teoríay los conceptos relacionados con la asig-natura. El poder experimentar con dichosconceptos mediante la aplicación de algo-ritmos debe ser una actividad que facili-te esa comprensión. Gracias a ToTalf, elalumno puede comprobar directamente siha realizado de manera correcta un ejerci-cio teórico. Además, en el caso de proble-mas de mayor tamaño, el alumno inviertesu tiempo en el análisis de los resultadosde los algoritmos, en vez de utilizarlo enrealizar trazas sobre papel.

• Ayuda en la realización de prácticas. Losalumnos pueden experimentar con los al-goritmos antes de acometer las prácti-cas que deben realizar. Pero fundamen-

222 Fundamentos teóricos de la informática

talmente, es un marco de comprobación.En general, los alumnos dedican muchotiempo a la implementación de las prác-ticas, pero poco a la comprobación de losresultados. Se suelen conformar con com-probar su código con los ejemplos que se lehan suministrado, lo cual a veces resultainsu�ciente. Con ToTalf se pretende queel alumno tenga de una manera sencillauna forma de examinar los resultados quedevuelve su programa.

• Así mismo, es útil en la realización deprácticas de cierta envergadura, en las quehaya que calcular ciertos resultados inter-medios, los cuales no son objetivo de es-tudio de la práctica.

• Puede ser también una herramienta in-teresante para aquellos alumnos curiososque gusten de experimentar por su cuen-ta.

3. ToTalf: la herramienta

3.1. Implementación

ToTalf está programado en Java. La elecciónde Java como lenguaje de programación res-ponde a la gran ventaja de su ejecución mul-tiplataforma, que permite su uso en multitudde entornos, con la ventaja de poder ejecutarsede manera sencilla y directa en un navegador.

Concretamente, ToTalf está programado enJava 1.4, y se proporciona tanto en versión ap-plet como en versión aplicación.

Para la ejecución del applet (es decir, la eje-cución a través del navegador) es necesario unnavegador con soporte para la máquina vir-tual Java de Sun [7]. Por lo tanto, se necesitadisponer del paquete J2RE (entorno de ejecu-ción de Java) o el paquete J2SDK (entorno dedesarrollo de Java), disponibles ambos en lasección de descargas.

Sin embargo, para un uso cotidiano, se reco-mienda la versión aplicación, que no está afec-tada por las restricciones de seguridad impues-tas a los applets. Con la versión aplicación po-dremos cargar y guardar archivos, y copiar ypegar entre aplicaciones y el applet, o vicever-sa. Para la ejecución de la aplicación, es ne-

cesario, al igual que antes, J2RE o J2SDK, ytambién descargar el �chero jar del proyecto.Los requisitos principales de la aplicación a

desarrollar fueron los siguientes:• Disponer de un sistema de ayuda para queel usuario pudiera consultar cómo operarcon la herramienta. La ayuda debe, ade-más, poder modi�carse con sencillez.

• Facilidad de introducción de nuevos algo-ritmos.

• Posibilidad de introducción de nuevosejemplos prede�nidos para cada tipo deconcepto.

• Desarrollo en Linux.Para cumplir el primer requisito, se optó porrealizar la ayuda de ToTalf en formato HTML.Se trata de una solución estándar y amplia-mente utilizada, ya que los �cheros de ayudase puede crear y modi�car fácilmente, más aúnteniendo en cuenta la multitud de herramien-tas disponibles en este campo.Se puso un especial énfasis en el diseño de

los objetos que representan los diferentes tiposde conceptos (o modelos de cómputo) con el�n de permitir la escalabilidad del programa.Cada objeto tiene abundantes métodos paramodi�car y acceder a las estructuras del mis-mo, de tal forma que implementar un nuevoalgoritmo sea una tarea sencilla.Se contempla el añadido de nuevos ejemplos

prede�nidos mediante la rede�nición de unatabla de conceptos prede�nidos en el código.Cada ejemplo se codi�ca al igual que se haceen la interfaz de usuario, con lo que es fácil lamodi�cación de dicha tabla.El último de los requisitos del proyecto fue

que se desarrollara sobre Linux, en un entornode desarrollo libre, ya sea en modo texto o grá-�co. A la vez, la herramienta o herramientas dedesarrollo debían ser de fácil uso, y que permi-tieran la modi�cación del código fuera de él, yde forma sencilla. La herramienta de desarrolloJBuilder8 Personal [6] se ajusta a estos pará-metros y está disponible gratuitamente parausos no comerciales.

3.2. Utilizando ToTalf

El tutorial contiene cuatro grandes módulosque abarcan los diferentes aspectos abordados

X Jornadas de Enseñanza Universitaria de la Informática 223

en la asignatura: automatas �nitos y expresio-nes regulares, gramáticas independientes delcontexto, máquinas de Turing y autómatas apila.En cada módulo el usuario puede introducir

una descripción textual del concepto corres-pondiente. Dicha descripción es igual a la quese utiliza en los enunciados de las prácticas,para facilitar el uso del programa a los alum-nos. Cada descripción puede guardarse en �-chero para su uso posterior, o también puedecargarse una descripción ya salvada. Se dispo-ne también de la opción de cargar unos ejem-plos prede�nidos, los cuales son representati-vos del concepto en cuestiónA la descripción introducida, se le pueden

aplicar los algoritmos implementados, que secorresponden con la totalidad de los algorit-mos programados en las prácticas de la asigna-tura más algunos otros interesantes estudiadosen clase.Describiremos a continuación cada uno de

los módulos que componen ToTalf.

• Autómatas �nitos y expresiones regula-res. En este módulo, se contemplan au-tómatas �nitos deterministas (AFD) y nodeterministas (AFN), al igual que un sub-conjunto de las expresiones regulares ex-tendidas. Se encuentran disponibles los si-guientes algoritmos:

• Transformación de AFN a AFD.• Eliminación de ε-transiciones.• Minimización de un AFD.• Obtención de un AFN a partir deuna expresión regular (Construcciónde Thompson).

• Obtención de una gramática regulara partir de un AFD.

• Obtención de los AFNs que recono-cen L(M1) ∪ L(M2) y L(M1)L(M2)a partir de los autómatas M1 y M2.

En las expresiones regulares, se reconocenlos operadores básicos (alternativas, con-catenaciones, asociaciones y cierre), juntoa varias características de los expresionesregulares extendidas: conjuntos de carac-teres (por ej. [abc], [a-c]), el cierre posi-tivo, el operador de interrogación y algu-

nas clases de conjuntos de caracteres (porej. [:alpha:] y [:digit:]).

• Gramáticas independientes del contexto(GIC). En este módulo, los algoritmos im-plementados son:

• Cálculo de los conjuntos �rst y fo-llow.

• Algoritmo de Cocke�Younger�Kasami para el análisis sintáctico deuna frase.

• Cálculo de la forma Normal deChomsky.

• Simpli�cación de una GIC.• Eliminación de la recursividad por laizquierda de una GIC.

• Transformación de una gramática re-gular lineal por la derecha a un AFN.

• Máquinas de Turing. En el módulo de má-quinas de Turing, el único algoritmo im-plementado es la simulación de una má-quina de Turing con una cinta in�nita enambos sentidos.

• Autómatas a pila deterministas. El únicoalgoritmo disponible es el de la simulaciónde un autómata a pila determinista.

3.3. Descripciones

En cada uno de los módulos de ToTalf, la en-trada a los diferentes algoritmos viene dadapor una descripción del modelo de cómputocorrespondiente.

// gramática que genera expres iones// r e gu l a r e s s imp lesER −> ER + ALT

ER −> ALT

ALT −> ALT PIEZA

ALT −> PIEZA

PIEZA −> ATOMO

PIEZA −> ATOMO ∗ATOMO −> t

ATOMO −> ( ER )

Listado 1: Fichero de representación de unagramática

Las descripciones tratan de ser lo más generaly �exible posible. Así, por ejemplo, el númerode caracteres prohibidos intenta ser mínimo,se permite el uso de comentarios en las des-cripciones, o en el caso de las gramáticas, los

224 Fundamentos teóricos de la informática

Figura 1: Autómata que reconoce cadenas con unno par de 'a' y que no contengan la subcadena'bbb'

símbolos pueden constar de más de un carác-ter.

Como ejemplo, el listado 1 muestra una des-cripción de una gramática que genera expre-siones regulares.

3.4. Un ejemplo de uso con autómatas

Supongamos que el alumno desea resolver el si-guiente problema: Dado el alfabeto Σ = {a, b}hallar un autómata �nito con un número mí-nimo de estados que reconozca las cadenas deΣ∗ que contengan un número par de símbolos'a' y no contengan la subcadena 'bbb'.

Cuando se les plantea este problema a losestudiantes, la mayoría obtienen directamentela solución, que se muestra en la �gura 1.

Sin embargo muchos otros alumnos tratande obtener la solución siguiendo un proceso al-ternativo, en el que ToTalf es una herramientamuy útil a la hora de simpli�car algunos de loscálculos que han de realizarse.

Para resolver este problema, puede resultarcómodo partir de dos autómatas que reconoz-can los siguientes lenguajes:

L1 = {w ∈ Σ∗|w contiene un número par desímbolos 'a'}

L2 = {w ∈ Σ∗|w no contiene la subcadena'bbb'}Los AFD que reconocen L1 y L2 son los que

aparecen en la �gura 2.

El autómata que se nos pide puede obte-nerse teniendo en cuenta la siguiente relación

Figura 2: Autómatas que reconocen L1 y L2

Figura 3: Autómata que reconoce L(M1)∪L(M2)

entre lenguajes, consecuencia de la aplicaciónde una de las leyes de Morgan:

L1 ∩ L2 = L1 ∪ L2

Dado un AFD M que reconoce un lenguajeL, para obtener el AFD que reconoce L bastacon cambiar en M los estados que son de acep-tación por estados que no sean de aceptacióny convertir en estados de aceptación aquellosque en M no lo eran.Por otra parte, partiendo de las descripcio-

nes de los autómatas M1 y M2 que reconocenL1 y L2 respectivamente, y utilizando uno delos algoritmos implementados en ToTalf, pode-mos obtener el AFN que reconoce L1 ∪L2. La�gura 3 muestra el fundamento teórico de estaconstrucción. Si aplicamos a este autómata elalgoritmo de conversión de un AFN en AFD yal resultado le aplicamos la minimización delnúmero de estados de un AFD, obtendremosel AFD que se muestra en la �gura 1, que esla solución del problema planteado.

3.5. Un ejemplo de uso con gramáticas

Supongamos otro caso real de trabajo: cons-truir un analizador sintáctico descendente re-

X Jornadas de Enseñanza Universitaria de la Informática 225

Figura 4: Gramática de expresiones regulares sinrecursividad por la izquierda

cursivo predictivo para la gramática del listado1.

El primer paso consiste en introducir la gra-mática y aplicar el algoritmo de eliminación dela recursividad por la izquierda. Tras seleccio-nar el algoritmo adecuado en el menú Algorit-mos, obtenemos el resultado en el marco de laderecha, tal y como se muestra en la �gura 4.

El siguiente paso a dar sería comprobarque con esta gramática sin recursividad porla izquierda se puede construir un analizadordescendente recursivo predictivo que funcione.Para ello, se debe cumplir que: ∀A ∈ V |A →αi|αj :

First(αi) ∩ First(αj) = ∅,∀i 6= jSi αi ⇒∗ ε, entoncesFirst(αj)∩Follow(A) = ∅,∀j No existe ac-

tualmente un algoritmo implementado en To-Talf que calcule esto, por lo que habría quehacerlo a mano. No obstante, sí está imple-mentado el cálculo de conjuntos �rst y followde una gramática, por lo que la tarea es mu-cho más sencilla. Los conjuntos de �rst y fo-llow se muestran en la �gura 5. Tras la correc-ta comprobación de que un analizador descen-dente recursivo predictivo puede funcionar conla gramática, el alumno puede empezar a co-di�car dicho analizador.

4. Conclusiones y trabajo futuro

La valoración que hacemos de los resultadosdel primer año de utilización de ToTalf enla docencia de TALF es absolutamente posi-

Figura 5: Conjuntos First y Follow de la gramáticade expresiones regulares

tiva. Las encuesta que hemos realizado entreel alumnado re�eja que una mayoría de elloshan utilizado la herramienta y también mayo-ritariamente quienes la han utilizado están sa-tisfechos con los resultados obtenidos. Para elpróximo curso, una vez cubierta la etapa en laque la primera versión de ToTalf ha sido pro-bada satisfactoriamente, planeamos utilizarlade forma más intensiva en el desarrollo de loscontenidos de la asignatura.

Nos gustaría también destacar que ToTalfestá siendo utilizado no sólo por los alum-nos matriculados en TALF sino también porlos alumnos de Compiladores, asignatura cu-yos contenidos están muy cercanos a los desa-rrollados en TALF.

Por otra parte consideramos que el trabajorealizado hasta ahora debe ser considerado co-mo un primer prototipo de la herramienta. Nosgustaría poder seguir perfeccionándola y so-bre todo añadiéndole funcionalidades que ac-tualmente no contempla. La lista de posiblesampliaciones a la herramienta es tan ampliacomo los contenidos objeto de estudio en lasasignaturas de TALF y Compiladores, pero enconcreto tenemos ya en mente contemplar lassiguientes extensiones:

• Obtención del autómata �nito (AF) quereconoce el lenguaje complementario delreconocido por otro AF.

• Equivalencia de AFs.

• Simulación de Autómatas a pila no deter-ministas (APND).

226 Fundamentos teóricos de la informática

• Obtención del APND asociado con unagramática independiente del contexto(GIC).

• Cálculo de la tabla LL(1) para una GIC.

• Obtención de la GIC que genera el len-guaje reconocido por APND.

• Simulación de máquinas de Turing con va-rias cintas.

Pero sin duda, una de los aspectos más intere-santes a incluir es una interfaz grá�ca para lade�nición de los autómatas, en vez del actualesquema de texto. La creación de autómatassería más intuitiva, y el análisis de los autó-matas resultado de los algoritmos, mucho mássencillo, lo que conllevaría un mejor entendi-miento por parte del alumno.

Tal como ha sido concebido, el prototipo ac-tual de ToTalf no es más que el núcleo básicode una herramienta que tiene toda la poten-cialidad de proseguir su desarrollo. En el casode herramientas similares, lo único que pode-mos hacer es recomendar a nuestros alumnossu utilización, mientras que ToTalf es un pro-totipo sobre el que tenemos control total. Tam-bién estamos considerando la posibilidad de li-berar el código fuente de la aplicación, hacién-dolo de dominio público, de forma que toda lacomunidad académica de habla hispana puedacontribuir al desarrollo de la herramienta.

En resumen, consideramos satisfactorio elesfuerzo invertido en este proyecto de calidaddocente. Pensamos que ToTalf es en estos mo-mentos una de las herramientas de estas carac-terísticas más completas desarrollada en Espa-ña, y que se ajusta plenamente a los objetivoscon los que fue concebida.

Referencias

[1] John E. Hopcroft and J. D. Ullman. In-troduction to Automata Theory, Langua-ges and Computation. Addison-Wesley,London, 1979.

[2] Susan H. Rodger. JFLAP 4.0b10 ver-sion. Disponible electrónicamente enhttp://www.cs.duke.edu/�rodger/tools/

jflap/index.html.

[3] MindSpring Software. ABCEZ (appletbased computability enlightenment zo-ne). Disponible electrónicamente enhttp://www1.cs.columbia.edu/�zeph/Compu

tabilityApplets/abcez.html.

[4] J. Calera. Applet Java para realizar di-versas operaciones con autómatas �nitos.Departamento de Lenguajes y SistemasInformáticos de la Universidad de Ali-cante. Disponible electrónicamente enhttp://www.dlsi.ua.es/asignaturas/lga/

applet/Afapplet.html.

[5] Francisco de Sande. Páginas webde Teoría de Autómatas y Len-guajes Formales. Escuela TécnicaSuperior de Ingeniería Informática.http://asignaturas.pcg.ull.es/etsii/

talf/.

[6] Jbuilder downloads.Disponible electrónicamente enhttp://www.borland.com/products/downloa

ds/download_jbuilder.html.

[7] Java. Página principal:http://java.sun.com.

[8] Nicolas Christin. DFApplet a deter-ministic �nite automata applet simu-lator. Disponible electrónicamente enhttp://www.cs.virginia.edu/�nc2y/dfa/.

[9] Dynalab. Finite State Automaton Ap-plet. Disponible electrónicamente enhttp://www.cs.montana.edu/�dynalab/fsa/

fsa.html.

[10] Thomas Dunn. Interactive ani-mation of �nite-state automa-ta. Disponible electrónicamente enhttp://www.ccs.neu.edu/home/tdunn/COM13

50/honors/.

[11] Román Sosa González. ToTalf tutorialonline de teoría de autómatas y lengua-jes formales. Disponible electrónicamenteen http://asignaturas.pcg.ull.es/etsii/

talf/ToTALF/Applet_ToTalf.html.