Antonio J. Tomeu Hardasmal (coordinador)

El diseño de traductores es en ocasiones una actividad necesaria en el ámbito
de la profesión de ingeniero informático, y en el plan de estudios de la
titulación se ha considerado así mediante el planteamiento de la asignatura
obligatoria de tercer curso Traductores. El diseño de varias fases de un
traductor se apoya en el conocimiento y uso de determinados modelos teóricos,
siendo aquí donde esta asignatura juega su papel, pudiendo entenderse como el
conjunto de previos teóricos que garantizan un seguimiento adecuado
de Traductores.

En función de lo expuesto, cabe plantear los siguientes objetivos académicos:

1. Conocer el concepto de gramática formal, de derivación en uno  y múltiples
pasos, y  de lenguaje generado por una gramática.
2. Saber describir un conjunto de entradadas dado (lenguaje) mediante una
gramática formal.
3. Conocer la Jerarquía de Chomsky.
4. Conocer el concepto de lenguaje regular,  y saber construir autómatas
finitos (en sus versiones  determinista, no determinista, y no determinista con
transiciones épsilon) que reconozcan a lenguajes regulares. Saber aplicar los
métodos de transformación entre las diferentes clases de autómatas finitos.
5. Saber describir un lenguaje regular mediante una expresión regular.  Dominar
el álgebra de las expresiones regulares. Conocer el algoritmo de Thompson para
pasar de una expresión regular a un autómata finito.
6. Conocer y saber aplicar en la práctica los principales resultados teóricos
de interés que afectan al universo de los lenguajes regulares: lema de bombeo,
propiedades de clausura y algoritmos de decisión.
7. Saber obtener la representación  mínima para cualquier autómata finito
determinista dado.
8. Conocer el  concepto de gramática libre del contexto, de lenguaje libre del
contexto, de árbol de derivación y de ambigüedad.
9. Saber escribir gramáticas libres del contexto que describan entradas propias
de un lenguaje de programación.
10.  Saber construir autómatas de pila que acepten a  lenguajes libres del
contexto  mediante pila vacía y mediante estados finales.
11. Conocer y saber aplicar los principales resultados teóricos de interés que
afectan al universo de los lenguajes libres del contexto: lema de bombeo,
algoritmos de simplificación, formas normales, propiedades de clausura y
algoritmos de decisión.

Contenidos del Programa Teórico

Tema 1: Autómatas Finitos, Expresiones Regulares y Gramáticas Regulares. (8
horas)
1.0 Introducción y Notaciones.
1.0.1 Alfabetos, lenguajes. Noción de gramática generativa.
1.0.2 Lenguaje generado por una gramática.
1.0.3 La jerarquía de Chomsky
1.1 Autómatas Finitos Deterministas.
1.1.1 Definición.
1.1.2 Lenguaje reconocido por un autómata finito.
1.1.3 Homomorfismos entre Autómatas Finitos.
1.2 Autómatas Finitos No Deterministas.
1.2.1 Definición.
1.2.2 Utilidad.
1.2.3 Equivalencia con el modelo determinista.
1.2.4 Introducción de las transiciones nulas.
1.2.5 Equivalencia con el modelo sin transiciones nulas.
1.3 Autómatas Finitos con Salida.
1.3.1 Máquinas de Moore.
1.3.2 Máquinas de Mealy.
1.3.3 Equivalencia.
1.4 Expresiones regulares.
1.4.1 Definición.
1.4.2 Ejemplos.
1.4.3 Teorema de Kleene (Equivalencia AF-ER).
1.5 Gramáticas regulares.
1.5.1 Definición.
1.5.2 Lenguaje generado por una gramática regular.
1.5.3 Equivalencia  entre las gramáticas regulares y los autómatas
finitos.

Tema 2: Propiedades de los Lenguajes Regulares. (7 horas)
2.1 Lema de bombeo para conjuntos regulares
2.1.1 Proposición y prueba del lema de bombeo.
2.1.2 Aplicabilidad. Argumento del adversario.
2.1.3 Ejemplos de aplicación.
2.2 Propiedades de clausura de los lenguajes regulares.
2.2.1 Unión, complementario y clausura de Kleene.
2.2.2 Intersección.
2.2.3 Homomorfismos.
2.3 Algoritmos de decisión para conjuntos regulares.
2.3.1 Vacuidad, finitud e infinitud.
2.3.2 Equivalencia.
2.4 Minimización de autómatas finitos.
2.4.1 El teorema de Myhill-Nerode.
2.4.2 Un algoritmo de minimización.
2.4.3 Ejemplos.
2.5 Aplicaciones del modelo de autómatas finitos.
2.5.1 Definiciones regulares en Unix.
2.5.2 Análisis Léxico.

Tema 3 : Autómatas de Pila y Lenguajes Libres del Contexto. (8 horas)
3.1 Gramáticas libres de contexto.
3.2 Árboles de Derivación.
3.2.1 Definición.
3.2.2 Construcción de árboles de derivación.
3.3 Ambigüedad.
3.3.1 Gramáticas ambiguas.
3.3.2 Eliminación de la ambigüedad.
3.2.3 Derivación más a la izquierda.
3.2.4 Ambigüedad inherente.
3.4 Autómatas de pila no deterministas.
3.4.1 Definición.
3.4.2 Descripciones instantáneas.
3.4.3 Lenguajes aceptados por pila vacía.
3.4.4 Lenguajes aceptados por estados finales.
3.4.5 Equivalencia de los mecanismos de aceptación.
3.5 Equivalencia formal autómatas de pila-gramáticas libres de contexto.
3.6 Introducción del determinismo en los autómatas de pila.
3.6.1 Definición de una autómata de pila determinista (APD).
3.6.2 Lenguajes Regulares y APD.
3.6.3 APD y Lenguajes independientes del contexto.
3.6.4 APD y Gramáticas ambiguas.

Tema 4: Propiedades de los Lenguajes Libres del Contexto. (7 horas)
4.1 Formas Normales
4.1.1 Eliminación de símbolos y producciones inútiles.
4.1.2 Eliminación de producciones nulas.
4.1.3 Eliminación de producciones unitarias.
4.1.4 Forma Normal de Chomsky.
4.1.5 Forma Normal de Greibach.
4.2 Lema de bombeo para lenguajes libres del contexto.
4.2.1 Proposición y prueba del lema de bombeo.
4.2.2 Aplicaciones.
4.2.3 El lema de Odgen.
4.3 Propiedades de clausura de los lenguajes libres de contexto.
4.3.1 Unión, encadenamiento y clausura de Kleene.
4.3.2 Sustituciones, Reflexión.
4.3.3 Intersección con un lenguaje regular.
4.3.4 Homomorfismo inverso.
4.3 Algoritmos de decisión para lenguajes libres de contexto.
4.3.1 Vacuidad, finitud e infinitud.
4.3.2 Pertenencia: algoritmo de Cocke-Younger-Kasami.
4.4 Aplicaciones de los Lenguajes Libres del Contexto.
4.4.1 Descripción sintáctica de los lenguajes de programación.
4.4.2 Análisis sintáctico.
4.4.3 Lenguajes de Marcado.
4.4.4 XML y la definición de tipos de documentos

Contenidos del Programa Práctico

Se realizarán clases de problemas sobre relaciones propuestas previamente,
introducciones a modelos de cálculo teórico adicionales, visitas de páginas
web de contenidos afines a la disciplina o de interés general, y prácticas con
simuladores de las estructuras teóricas explicadas a lo largo del curso
mediante el uso del software  JFLAP.

La temporización que se propone para el programa práctico es la siguiente:

1. Simulación de Gramáticas con JFLAP  1 hora
2. Problemas del Tema 1  3 horas
3. Problemas del Tema 2  2 horas
4. Simulación de Autómatas Finitos en JFLAP  2 horas
5. Expresiones Regulares en JFLAP  1 hora
6. Minimización de Autómatas Finitos Deterministas con JFLAP  1 hora
7. Problemas del Tema 3  2 horas
8. Simulación de Autómatas de Pila en JFLAP  1 hora
9. Problemas del Tema 4  2 horas
Total:  15 horas

-Clases teóricas.
-Clases de problemas.
-Prácticas de laboratorio.

En los contenidos teóricos se insistirá en el uso de una metodología
orientada al razonamiento formalizado y simbólico con el objeto de desarrollar
en el alumno sus capacidades deductivas y de abstracción. Dichos contenidos se
cubrirán por tanto mediante clases teóricas basadas en un esquema expositivo
formal. Los contenidos prácticos, en cambio, recibirán un enfoque totalmente
diferente, y estarán orientados hacia la resolución de relaciones de
problemasy a la utilización de simuladores de los modelos explicados durante el
curso.

El alumno dispondrá de cronogramas de teoría y prácticas orientativos, donde se
recogerá, al menos, la siguiente información:

a) Fecha prevista para impartir cada tópico concreto del programa.
b) Material de lectura mínimo recomendado para preparar la clase.
c) Conjunto de lecturas y ejercicios para consolidar el tópico de que se trate
d) Fechas de interés: entrega de asignaciones, exámenes, etc.

Aa evaluación tendrá en cuenta los siguientes componentes:

a)Examen Final de la Asignatura: conteniendo preguntas teóricas cortas y
problemas, con un tiempo de duración nunca superior a las 3 horas, y durante
el cual se permite al alumno el uso de apuntes de clase y bibliografía
libremente. La Convocatoria Oficial se hará pública en el tablón del
Departamento, en la página web de la asignatura, y en el Campus Virtual de la
misma.
b)Asignaciones de Prácticas: se plantearán asignaciones de prácticas que
el alumno resolverá mediante los simuladores adecuados, remitiendo los
ficheros solución resultantes al profesor en la fecha y forma que este
determine. Su realización es obligatoria. Su calificación, consideradas
globalmente será de APTO o NO APTO.

La calificación final de la asignatura vendrá determinada por la calificación
obtenida en el examen final,siempre que se haya obtenido APTO en prácticas.

El alumno debe conocer además que la evaluación se regirá por las siguientes
normas adicionales:

1)La entrega de las asignaciones de prácticas en la fecha, hora y formato de
entrega determinados por el profesor es obligatoria para superar la asignatura.
Se admitirá un retraso de hasta 24 horas sobre la fecha
prevista de entrega, pero minorando la calificación en un 20%. Entregas fuera
de este plazo no se admitirán, y la calificación otorgada será de cero puntos.
En caso de enfermedad o fuerza mayor documentalmente justificadas, el profesor
indicará al alumno nueva fecha de entrega.
2)Es necesario tener superadas las prácticas para poder aprobar la
asignatura.
3)La calificación de las prácticas será de APTO o NO APTO. En este
último caso el alumno deberá concurrir a un examen práctico de acuerdo a
convocatoria hecha pública por el Centro, de duración no mayor de 90 minutos
en el que se permitirá el uso de apuntes y material bibliográfico. El
resultado del citado examen será igualmente de APTO o NO APTO.
4)Los exámenes finales de Junio y Septiembre se regirán por los
Estatutos de la Universidad de Cádiz en cuanto a número de convocatorias y
días de revisión de calificaciones se refiere.
5)A toda convocatoria se acude con el temario completo (tanto teórico como
práctico). No se reservarán calificaciones de partes de la asignatura para
convocatorias sucesivas.
6)Para lo no contemplado en estas notas se estará a lo dispuesto en el
Reglamento de Régimen Académico y Evaluación del Alumnado de la Universidad de
Cádiz.

BIBLIOGRAFÍA BÁSICA

[Alf87] Alfonseca, M., Sancho, J. y Martínez, M. Teoría de Lenguajes,
Gramáticas y Autómatas. Ediciones Universidad y Cultura, 1987.

[Bro93] Brookshear, J. Teoría de la Computación: lenguajes formales, autómatas
y complejidad. Addison-Wesley Iberoamericana, 1993.

[Dav94] Davis, M., Sigal, R. and Weyuker, E. Computability, Complexity and
Languages. Academic Press, 1983. (Hay segunda edición de 1994).

[Hop02] Hopcroft, J., Motwani, R. u Ullman, J. Introducción a la Teoría de
Autómatas, Lenguajes y Computación. Addison-Wesley, 2002.

[Kel95] Kelley, D. Teoría de Autómatas y Lenguajes Formales. Prentice Hall,
1995.

[Ram03] Ramos, G. Apuntes de Teoría de Autómatas y Lenguajes Formales I.
Servicio de Publicaciones de la Universidad de Málaga, 2003.


BIBLIOGRAFÍA DE CONSULTA

[Aho92] Aho, A. and Ullman, J.D. Foundations of Computer Science. W. H.
Freeman and Company. New York, 1992

[Bil93] Billington, D. Using the context-free pumping lemma. Commun. ACM, 36
(6), 21-ff, 1993.

[Cal88] Calude, C. Theories of Computational Complexity. North-Holland, 1988.

[Car89] Carroll, J. and Darrell, L. Theory of Finite Automata with an
Introduction to Formal Languages. Englewood Cliffs, NJ. Prentice Hall, 1989.

[Coh91] Cohen, D. Introduction to Computer Theory. John Wiley and Sons, Inc.
1991.

[Deh93] Dehornoy, P. Complexite et decidabilite. Springer-Verlag, 1993

[Dro89] Drobot, V. Formal Languages and Automata Theory. Computer Science
Press, 1989.

[Fer95] Fernández, G. y Sáez, F. Fundamentos de Informática: lógica,
autómatas, algoritmos y lenguajes.  Anaya Multimedia, 1995.

[Gar79] Garey, M and Johnson, D. Computers and Intractability: a guide to the
theory of NP-completness. New York, Freeman, 1979.

[Hop79] Hopcroft, J. and Ullman, J. Introduction to Automata Theory, Languages
and Computation. Addison-Wesley, 1979.

[How91] Howie, J. M. Automata and Languages. Oxford University Press. Oxford,
1991.

[Jon97] Jones, N. D. Computability and Complexity. The MIT Press, 1997.

[Lee90] Leeuwen, J. V. (ed.) Handbook of Theoretical Computer Science.
Elsevier, 1990.

[Lew91] Lewis, H and Papadimitriou, C. Elements of the Theory of Computation.
Englewood Cliffs, NH. Prentice Hall, 1991.

[Lin90] Linz, P. An Introduction to Formal Languages and Automata. Lexington,
MA. D.C. Health and Company, 1990.

[Mar91] Martin, J. Introduction to Languages and the Theory of Computation.
New York, McGraw-Hill, 1991.

[Mcn82] McNaughton, R. Elementary Computability, Formal Languages and
Automata. Prentice Hall, 1982.

[Rev83] Revesz, G. Introduction to Formal Languages. McGraw-Hill, 1983.

[San90] Sancho, J. Lógica Matemática y Computabilidad. Díaz de Santos, S.A.,
1990.

[Som88] Sommerhalder, R. and Van Westerhenen S. C. The Theory of
Computability : Programs, Machines, Effectiveness and Feasibility. Addison-
Wesley, 1988.

[Sud88] Sudkamp, T. Languages and Machines, An Introduction to the Theory of
Computer Science. Addison-Wesley Series in Computer Science. Readin, MA.
Addison-Wesley Inc 1988.

[Wil86] Wilf, H.S. Algorithms and Complexity. Prentice-Hall, 1986.

[Woo87] Wood, D. Theory of Computation, New York, John Wiley & Sons, 1987.