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, con asistencia ocasional de medios audiovisuales.

Los contenidos prácticos, en cambio, recibirán un enfoque totalmente
diferente, y estarán orientados hacia la resolución de relaciones de
problemas y a la utilización de simuladores de los modelos explicados durante
el
curso.

Con frecuencia semanal o bisemanal el alumno se enfrentará a la resolución de
un
conjunto de ejercicios prácticos, que juntos constituyen una asignación (o
entregable) de prácticas, que será puesto a disposición del profesor para su
corrección únicamente por los medios electrónicos que la plataforma virtual de
la UCA oferta.

Semanalmente el profesor hará público en el Campus Virtual el conjunto completo
de actividades en aula y fuera de ella que el alumno debe desarrollar para una
correcta compresión de los contenidos que se van a impartir en la semana,
incluyendo:

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) Actividades complementarias de interés.

La 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 y en el Campus Virtual de la asignatura.

b)Asignaciones de Prácticas: se plantearán asignaciones de prácticas que
el alumno resolverá mediante los simuladores adecuados o los programas que deban
desarrollarse, remitiendo los ficheros solución junto con los documentos que se
especifiquen en los enunciados al profesor en la fecha y forma que este
determine. Su realización y entrega es obligatoria, y tendrán siempre carácter
individual. Su calificación, consideradas individualmente, será de APTO o NO
APTO. Se obtiene APTO globalmente en prácticas cuando al menos el 70% de las
mismas han sido calificadas con APTO.

c)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 TODAS las asignaciones de prácticas propuestas en la fecha, hora
y formato de entrega determinados por el profesor ES REQUISITO DE PARTICIPACIÓN
de obligado cumplimiento para superar la asignatura, según establece el art. 2.1
del Reglamento de Evaluación de la UCA. 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, dándose la práctica por no
presentada. En caso de enfermedad o fuerza mayor documentalmente justificadas, el
profesor indicará al alumno nueva fecha de entrega.

2)Es necesario tener entregada y 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, y SIEMPRE QUE SE HAYAN ENTREGADO TODAS LAS PRÁCTICAS, el alumno
podrá 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. Para aquellos alumnos que tengan prácticas sin
entregar, se considerará que no han cumplido con los requisitos de participación
fijados en este instrumento de programación, a los efectos previstos en el art.
2.1 del Reglamento de Evaluación del Alumnado.

4)Los exámenes finales de Febrero, Junio y Septiembre se regirán por los
Estatutos de la Universidad de Cádiz y normativa derivada 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.

[Alf07] Alfonseca, M., Alfonseca, E. y Moriyón, R. Teoría de Autómatas y
Lenguajes Formales. McGraw-Hill, 2007.


[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.