Modelos informaticos

Modelos de computación 1. Prácticas

Pag. 1

Modelos de Computación I

Ingeniería Informática

Práctica 1
Curso 2005-2006

Profesores: Serafín Moral Callejón Carlos J. Mantas Ruiz

Modelos de computación 1. Prácticas

Pag. 2

Normativa general de las practicas
Se propone la realización de dos prácticas sobre lenguajes: • • • • • • Se realizarán en grupos de dos personas. Cadagrupo pensará y propondrá un problema propio. Una práctica consistirá en el estudio de un lenguaje regular y la segunda de un lenguaje independiente del contexto. Se podrán usar las herramientas JFLAP (simulador de autómatas en Java) y Kakuy (procesador de gramáticas). Habrá que entregar un informe en papel, con el estudio que se haya realizado y la implementación en las herramientas utilizadas.Se valorará la importancia del problema, su originalidad, el estudio teórico y su implementación.

Modelos de computación 1. Prácticas

Pag. 3

Práctica 1
Ejecutar JFLAP
Para conseguir lanzar JFLAP en las aulas de prácticas de la escuela tenemos que realizar los siguientes pasos: 1. 2. 3. 4. 5. Entrar con el sistema operativo Linux (Red hat 7.0). Ejecutar el comando “startx”. Abrir unterminal de comandos. Acceder al directorio /fenix/depar/ccia/mc. Ejecutar el comando “java –jar JFLAP.jar”.

(Los pasos 4 y 5 en Red hat 7.1 corresponden al comando: /usr/local/jdk1.3.1/bin/java –jar /fenix/depar/ccia/mc/JFLAP.jar )

Ejercicios
• • • • • Pensar un problema original. A partir de él, se definirá un lenguaje regular cuyas cadenas tengan una aplicación particular en el problemapropuesto. Encontrar una gramática regular por la derecha que genere el lenguaje regular anterior. Definir una expresión regular que lo represente. Construir un autómata finito determinista mínimo que acepte las cadenas del lenguaje regular. Implementar en JFLAP los conceptos anteriores.

Ejercicio opcional • Insertar, de manera correcta, la expresión regular obtenida en esta práctica en lalibrería de expresiones regulares que se encuentra en la siguiente dirección: http://regexlib.com

Evaluación de la práctica 1
Se debe entregar: • • • • • Explicación del problema original que se plantea y su relación con un lenguaje regular. Gramática regular por la derecha que genera el lenguaje regular planteado. Expresión regular que lo representa. Autómata Finito Determinista mínimo queacepte sus cadenas. Disquete o disco con la implementación en JFLAP de los conceptos anteriores.

Para superar esta práctica el alumno/a deberá entregarla y defender sus implementaciones antes del día 16 de diciembre de 2005 en las horas de prácticas de la asignatura.

Modelos de computación 1. Prácticas

Pag. 4

Práctica 2
Ejecutar KAKUY
Para trabajar correctamente con Kakuy en las aulasde prácticas de la escuela tenemos que realizar los siguientes pasos: 1. Entrar en el sistema operativo Windows 2. Instalar Kakuy en el disco duro de nuestro ordenador de prácticas: (H:\ccia\mc\instalar_kakuy.exe). 3. Ejecutar Kakuy. 4. En el menú “opciones opciones generales” en el apartado “carpeta de Graphviz” especificar el directorio “H:\ccia\mc\bin”.

Ejercicios
• Pensar un problemaoriginal. A partir de él, se definirá un lenguaje libre de contexto (que no sea regular) que corresponda a ciertas pautas de comportamiento correctas del problema propuesto. Encontrar una gramática libre de contexto limpia (sin producciones inútiles, sin producciones nulas, sin producciones unitarias, sin recursión a la izquierda y sin ciclos) que genere el lenguaje anterior. Transformar la gramáticaanterior a Forma Normal de Chomsky y a Forma Normal de Greibach. Presentar dos cadenas de símbolos terminales u y v tales que: u pertenece al lenguaje que se está estudiando. v no pertenece al lenguaje que se está estudiando. • • Comprobar la pertenencia de u y de v con el algoritmo YCK y el algoritmo de Earley. Visualizar el árbol de derivación que genera la cadena u. Implementar los conceptos...