Ensayo

Teoría de Autómatas y Lenguajes Formales.

Prácticas Introducción a JFLAP


 
Teoría
 de
 Autómatas
 y
 
Lenguajes
 Formales
 
Prácticas
 
Introducción
 a
 JFLAP
 

Autores:
Araceli Sanchis de Miguel
Agapito Ledezma Espino
Jose A. Iglesias Martínez
Beatriz García Jiménez
Juan Manuel Alonso Weber

* Algunos ejercicios están basados en enunciadosdel siguiente libro:
• Susan H. Rodger and Thomas W. Finley. JFLAP: An Interactive Formal
Languages and Automata Package. Jones & Bartlett Publishers, Sudbury, MA
(2006).

1

Teoría de Autómatas y Lenguajes Formales.

Prácticas Introducción a JFLAP

JFLAP (del inglés, Java Formal Language and Automata Package) es un software
que permite experimentar de forma gráfica con los conceptosrelativos a la teoría de
autómatas y lenguajes formales. Permite diseñar, evaluar y realizar distintas
transformaciones y comprobaciones sobre autómatas finitos, gramáticas, autómatas a pila,
máquinas de Turing, y otros elementos adicionales que no forman parte del contenido de
este curso.
Para la realización de estas prácticas se requiere la descargar de la herramienta libre
JFLAP de su sitioweb (http://www.jflap.org/). Además es necesario consultar el tutorial
on-line de la herramienta (http://www.jflap.org/tutorial/), o el siguiente libro guía:
Susan H. Rodger and Thomas W. Finley. JFLAP: An Interactive Formal
Languages and Automata Package. Jones & Bartlett Publishers, Sudbury, MA
(2006).

NOTA IMPORTANTE: Para los ejercicios de limpieza y bien formación de gramáticas,
sedebe tener en cuenta la siguiente correspondencia entre la nomenclatura y orden de
pasos de la explicación teórica y ejercicios, y el proceso utilizado en la herramienta
JFLAP, acorde a la siguiente tabla.
Algoritmo
Reglas
innecesarias
Símbolos
inaccesibles
Reglas
superfluas

Símbolos no
generativos

Reglas no
generativas
Reglas de
redenominación

JFLAP

Explicación
teóricaDiferencia

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

Eliminación de
Reglas
innecesarias
Eliminación de
símbolos
inaccesibles

No hay

Eliminación de
reglas superfluas

No hay

Eliminación de
símbolos no
generativos

λ−production
removal

Eliminación de
reglasno
generativas
Eliminación de
Reglas de
redenominación

En clase se proporciona
un algoritmo distinto.
Poner el presunto
símbolo no generativo
como axioma: si se
obtiene lenguaje vacío,
entonces es no
generativo
No hay

Comentarios

Unit
production
removal

----No hay
-----

----El símbolo no
generativo, si está en
la parte derecha de
una regla de
gramática G2, G3puede eliminarse
tratando esta regla
como superflua.
----No hay
-----

2

Teoría de Autómatas y Lenguajes Formales.

Prácticas Introducción a JFLAP

1. Dada una gramática para generar números naturales:
G = ({0,1,2,3,4,5,6,7,8,9,0}, {N, C}, N, P)
P = { N ::= CN | C,
C ::= 0|1|2|3|4|5|6|7|8|9 }
Comprobad con el derivador múltiple por fuerza bruta (opción Input → Multiple Brute
ForceParse) qué secuencias son palabras del lenguaje L(G) y determinar el motivo.
Anotad las observaciones que realicéis en cada caso, con el derivador por fuerza bruta
simple (opción Input → Brute Force Parse).
Palabras de prueba

0

00

001

123

1234

12345

9212

43.34

2. Crear una gramática G que genere números reales, con “.” para separar la parte entera y
la fraccionaria.Comprobad qué secuencias de las siguientes son palabras del lenguaje
L(G) y determinar el motivo. Anotad las observaciones que realicéis en cada caso.
Palabras de prueba

0

00

00.1

3445

1.23

9.21.2

9..1

9,1

3. Obtención de Lenguajes. Escribe las siguientes gramáticas en el editor de JFLAP, y para
cada una de ellas haz:
a) una lista de 5 palabras que son aceptadas,...