Antonio J. Tomeu Hardasmal (coordinador)

El diseño de traductores es en ocasiones una actividad necesaria en el ámbito
de la Ingeniería Informática, 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 de computación,
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.
1.0 Introducción y Notaciones. (8 horas)
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 gramáticas regulares-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 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. (6 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.

Tema 5 : Máquinas de Turing. (1 hora)
5.1 Definición de Máquina de Turing.
5.1.1 Configuraciones. Computación.
5.1.2 El Lenguaje de una Máquina de Turing.
5.2 Máquinas de Turing y Computabilidad.
5.2.1 Funciones Turing-computables.
5.2.2 Tesis de Church-Turing.


Contenidos del Programa de Prácticas

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 los constructos teóricos explicados a lo largo del curso
mediante el uso del software gratuito JFLAP.

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 los constructos teóricos explicados 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:

TEMARIO PRÁCTICO
HORAS
1. Problemas del Tema 1  3 horas
2. Problemas del Tema 2  2 horas
3. Simulación de Autómatas Finitos en JFLAP  2 horas
4. Expresiones Regulares en JFLAP  1 hora
5. Minimización de Autómatas Finitos Deterministas con JFLAP  1 hora
6. Problemas del Tema 3  2 horas
7. Simulación de Autómatas de Pila en JFLAP  1 hora
8. Problemas del Tema 4  2 horas
10. Simulación de Máquinas de Turing en JFLAP  1 hora
Total  20 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 problemas, visitas a páginas web afines a la disciplina, y 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.

La asignatura admite dos modelos de evaluación que el alumno elige libremente
al inicio de la misma.

Por defecto, y siempre que el número de alumnos lo permita, se seguirá el
método de evaluación continua, tal y como lo establece el Reglamento de
Régimen Académico y Evaluación del Alumnado de la Universidad de Cádiz en su
artículo 11.3, de acuerdo a un subconjunto de los criterios siguientes:

a)Participación activa del alumno en clase.
b)Superación de todos los casos prácticos.
c)Superación de todas las asignaciones de problemas propuestas.
d)Confección y entrega de una memoria de prácticas.
e)Confección y entrega de una memoria de teoría.
f)Trabajos adicionales bajo la dirección del profesor.


Las entregas de asignaciones de problemas o de ejercicios prácticos tendrán
lugar en la fecha y hora límite determinada por el profesor, y comunicada
oportunamente a los alumnos por e-mail o a través de la página web de la
asignatura, siempre con la antelación que el Reglamento de Régimen Académico y
Evaluación del Alumnado establece. Se admitirá un retraso en la entrega de
hasta 24 horas, pero minorando la calificación en un 20%, salvo que el retraso
sea justificable documentalmente. La omisión de entregas sin justificar
determinará la exclusión del modelo de evaluación continua y el paso al modelo
ordinario

En otro caso, bien por elección del alumno, bien por exclusión del modelo de
evaluación continua, los alumnos tienen a su disposición el modelo de
evaluación ordinaria, con examen final según establecen los Estatutos de la
Universidad de Cádiz.

1)Dicho examen final tendrá dos partes: un conjunto de cuestiones
teóricas sobre contenidos y un apartado de problemas. La calificación será la
media de las dos partes, siempre que ambas superen un mínimo de 4.5 puntos.
2)Se permite el uso de apuntes/bibliografía para la realización del
examen.
3)Es necesario tener superadas las prácticas para poder aprobar la
asignatura.
4)La calificación de las prácticas será de APTO  o NO APTO.
5)Aquellos alumnos que no superen dos o más casos prácticos deberán
realizar un examen de prácticas. Su resultado será igualmente de APTO  o NO
APTO.
6)La nota final de la asignatura bajo evaluación continua será la media
ponderada de todos los aspectos que contribuyen a ella, siempre que en
prácticas se haya obtenido la calificación de APTO, y de acuerdo a lo
siguiente: memoria de teoría hasta 4 puntos; asistencia y participación hasta
2 puntos; asignaciones de problemas: hasta 4 puntos. La calificación así
obtenida se podrá matizar en función de otros criterios de evaluación continua
que se hubieran considerado, a criterio del profesor.
7)La nota final de la asignatura bajo  evaluación ordinaria será igual a
la calificación obtenida en el examen de la asignatura, siempre que en
prácticas se haya obtenido la calificación de APTO.
8)En caso de superar el temario teórico y no el práctico o viceversa, se
guardará la calificación de la parte aprobada hasta la convocatoria de
Diciembre, y constará como SUSPENSO (4.0) en las actas de la convocatoria
correspondiente.

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.

RECURSOS DE INFORMACIÓN
Son recursos disponibles en forma de páginas web en Internet. Se encuentran
recogidos mediante enlaces en la sección ?Enlaces? de la página web de la
asignatura. El url directo a estos recursos es:

http://www.geocities.com/atomeua/enlacestalf.html