Profesores

ANTONIO J. TOMEU HARDASMAL (Coordinador)

Situación

Prerrequisitos

El alumno debería tener una madurez matemática y como programador
razonable, resultado de haber cursado y superado asignaturas de primer
curso como Álgebra y Matemáticas Discretas.
Igualmente debería dominar el lenguaje C y ser capaz de implementar
código que simule modelos de pequeña complejidad. resultado de haber
cursado las asignaturas de primer curso Introducción a la Programación
y Metodología de la Programación. El conjunto de prerrequisitos se
concreta en los siguientes apartados:

a) Dominio de los conceptos básicos de teoría de conjuntos y del
léxico matemático estándar.
b) Dominio de técnicas básica de demostración: inducción, reducción al
absurdo.
c) Dominio de aritmética modular básica.
d) Dominio de la teoría de grafos básica.
e) Soltura con el uso del compilador del lenguaje C
f) Capacidad de simulación e implementación en C de programas de
complejidad y extensión media.

Contexto dentro de la titulación

Optativa de segundo curso.

Recomendaciones

Se hacen al alumno las siguientes recomendaciones:

1) Para los distintos temas del curso se le propondrán como material
de revisión/trabajo/estudio referencias concretas. También se le
proporcionarán unos apuntes, que como mucho debería usar como material
de apoyo, pero nunca como texto base.

2) La copia de apuntes en clase ES UNA PÉRDIDA DE TIEMPO: por tanto,
como profesor haré lo posible para que no tenga que copiar apuntes en
clase, proporcionándole en la página de la asignatura con carácter
previo a su explicación todo el material necesario para la preparación
de la misma. En consecuencia, si copia apuntes, es porque es usted un
copiador compulsivo; pero sepa que distraen su atención y suelen ser
fuente de errores en el estudio posterior, ya que lo que se copia mal
se estudia peor.

3) Una clase comienza antes de ser explicada y continua tras ser
explicada: o lo que es lo mismo, llegar a clase a ver qué nos cuenta
hoy este buen señor es un error. La mecánica de trabajo que les
recomiendo a lo largo del curso para preparar una clase debe seguir
las siguientes fases:

1. Lectura y revisión previa de los materiales indicados en el
cronograma del curso para esa clase en concreto. Dicho cronograma
estará disponible en la página virtual del curso cuando comience este.
En él se establecerá la fecha (aproximada) donde se impartirá cada
tópico del temario oficial, el material de lectura para esa clase en
concreto, los problemas recomendados para ejercitar los contenidos
teóricos explicados, y en ocasiones alguna tarea adicional de interés.

2. Asistencia a clase. Dado que no necesita tomar apuntes, preste
atención a los desarrollos y explicaciones del profesor, y
relaciónelos con lo previamente leído por usted. Tome notas de la
dudas o discrepancias que le surjan, para su posterior discusión en la
propia clase o en una tutoría individualizada.

3. Tras la clase, repase los contenidos de la misma, entiéndalos y
aclare con el profesor los conceptos que no estén claros. Póngalos en
práctica con los problemas de la relación que corresponda, y
conéctelos con los contenidos a desarrollar en la próxima clase. Es
decir, GO TO apartado 1.

3) Una asignatura NO se prepara en una semana. NO deje la preparación
del mismo para los últimos días. Probablemente será inútil. Pida ayuda
a su profesor para planificar el tiempo y su preparación de cara al
examen final  con antelación. Si no lo hace, el único perjudicado será
usted.

5) Saber una asignatura NO es saber unos apuntes. Unos apuntes son,
probablemente y en el mejor de los casos, un resumen de lo explicado
por el profesor en clase, lo cual a su vez será un resumen de lo
revisado por el profesor en la bibliografía específica. Por tanto,
olvide aquello de "me sé los apuntes pero me han suspendido", o "esto
no estaba en los apuntes, sino en tal libro" o "este problema no se
parece a  ninguno que hayamos hecho en clase". Si usted  SABE la
materia, estará preparado para aplicarla a situaciones nuevas y
desconocidas. Y ello pasa por haber manejado bibliografía tal y cómo
se indica en el criterio 1. Saber los apuntes es una condición
necesaria para aprobar, pero no suficiente. Por tanto, si usted sabe
sus apuntes, NO SABE la materia. Y recuerde que SABER no es MEMORIZAR.

6) La revisión de calificaciones NO es una subasta. La directriz que
debe motivarle a solicitar y revisar sus calificaciones es saber
DÓNDE, CÓMO Y POR QUÉ ha fallado, y PLANIFICAR con su profesor la fase
posterior de estudio orientada a subsanar esos fallos. Por tanto, por
favor, no acuda a revisión con la intención de discutir sobre:

1. Los criterios de corrección, ya que estos los define su
profesor, y no es ni puede ser algo sujeto a negociación.

2. La distribución de la puntuación entre los diferentes
enunciados de los ejercicios del examen, ya que su profesor sabe qué
es más importante que usted haya aprendido, y cómo evaluar ese
aprendizaje, y ajustará esa distribución en consecuencia. El que
considere que esa distribución le perjudica es un error, ya que habrá
sido aplicada por igual a sus compañeros, y además lo que hará
será demostrar que no tiene claros aquellos conceptos que son más
relevantes.

3. Lo parecido o distinto de los ejercicios del examen a los
realizados en clase. (Ver principio 5)  Un examen no tiene por qué
parecerse a lo ya ejercitado. Los ejercicios de clase  le CAPACITAN
para dominar los conceptos. Los exámenes DEMUESTRAN que usted sabe
aplicar esos conceptos aprendidos a situaciones novedosas o
simplemente diferentes a las estudiadas.

4. La verificación de si determinado ejercicio estaba o no en sus
apuntes (Ver principio 5)
5. La simple pataleta por no haber superado la asignatura. No
entienda un suspenso más que con la siguiente lectura: el trabajo
realizado ha sido válido, pero no suficiente. Debe trabajar más.
Cualquier otra interpretación por su parte es un error (Ver principio
10)
7) Procure estar informado. Visite con asiduidad la sección de
noticias del web de la asignatura y en caso de duda consulte por e-
mail a su profesor. No utilice argumentos de "no sabía nada..." o "no
me he enterado de que.." para excusar un fallo. Recuerde que ES su
obligación y su responsabilidad estar enterado.

8) Utilice la tutoría. Es el único medio por el cual el profesor puede
ofrecerle una enseñanza de carácter individualizado. Por tanto,
aproveche la tutoría, en sus versiones presencial, electrónica, o vía
el foro de la asignatura. Y hágalo con frecuencia: siga el método
descrito en el principio 3 y visite a su profesor cada vez que tenga
dudas. Con carácter ordinario, un mínimo de una visita al profesor
cada tres semanas debería ser normal para usted. Si hay dificultades,
tan a menudo como necesite.

9) NO se quede con una duda. Es muy habitual entre nuestros alumnos
que cuando les surge una duda se queden con ella hasta el mismo
momento del examen. Luego, durante la revisión reconocen: "sí, esto no
me quedó claro, pero..."  EVITE estos comportamientos. En una
asignatura como esta, el progreso con garantías hacia nuevos
contenidos implica haber asimilado correctamente los contenidos
previos.

10) El profesor es su juez, NO es su verdugo. Mi labor en el momento
de evaluarle se limitará a juzgar la cantidad y calidad del esfuerzo
realizado por usted. Cualquier otro aspecto es irrelevante.

11) Participe en clase. Plantee sus dudas, y fomente la discusión
entre sus compañeros y con el profesor. Ello contribuirá de forma
positiva a su evaluación continua, y hará la dinámica académica más
rica. Además, contribuirá positivamente a su crecimiento personal.

12. Sea consciente de sus derechos como alumno, pero también de las
obligaciones que el serlo conlleva.

Competencias

Competencias transversales/genéricas

- Análisis y síntesis de contenidos técnicos
- Lectura comprensiva y escritura comprensible
- Determinación del ámbito de la solución de un problema
- Elección del nivel de abstracción de solución de un problema
- Capacidad de planificación temporal de tareas
- Elaboración de juicios críticos sobre contenidos
- Capacidad de elaborar documentación técnicamente correcta

Competencias específicas

• Cognitivas(Saber):

  -Dominar la terminología específica de la materia.
  -Conocer el concepto de gramática formal.
  -Conocer el concepto de lenguaje regular.
  -Conocer el concepto de autómata finito.
  -Dominar el álgebra de las expresiones regulares.
  -Conocer el  concepto de gramática libre del contexto, de lenguaje
  libre del contexto, de árbol de derivación y de ambigüedad.
  
  

• Procedimentales/Instrumentales(Saber hacer):

  -Manejar con competencia un cuerpo bibliográfico mínimo (3-4
  referencias) como fuente de apoyo al aprendizaje de la materia.
  -Redactar correctamente documentación de contenido técnico de
  acuerdo a formatos predefinidos
  -Diseñar gramáticas que describan conjuntos de entradas.
  -Escribir máquinas abstractas (autómatas) que acepten conjuntos de
  entradas dados.
  -Utilizar software de simulación de propósito específico (JFLAP,
  Kakuy y RegEx Coach) como herramientas de ayuda en las tareas
  anteriores.
  -Utilizar software de propósito general (compilador de C) como
  herramienta para simular máquinas abstractas de estado finito.
  

• Actitudinales:

  -Autoaprendizaje e independencia de criterio.
  -Conciencia crítica sobre el trabajo propio bien hecho.
  -Conciencia de la necesidad del esfuerzo y el trabajo personal como
  medio de lograr los objetivos fijados.
  -Conciencia de la necesidad de cumplir en tiempo y forma con plazos
  prefijados, normas de redacción y entrega de productos, etc.
  -Conciencia de la necesidad de cumplir con las obligaciones en
  materia de asistencia a clase, trabajo personal, rendimiento y
  espíritu universitario que la legislación universitaria actualmente
  en vigor establece para el alumnado.
  

Objetivos

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. Escribir gramáticas formales que describan conjuntos de entradas, y
realizar
derivaciones en uno  y múltiples pasos.
2. Escribir gramáticas que describan estructuras de control concretas de
lenguajes de programación conocidos.
3. Desarrollar tabularmente la Jerarquía de Chomsky y ser capaz de listar
sus implicaciones teóricas.
4. Dibujar autómatas finitos (en sus versiones  determinista, no
determinista, y no determinista con transiciones épsilon) que reconozcan a
lenguajes regulares dados. Aplicar los métodos de transformación entre las
diferentes clases de autómatas finitos.
5. Describir un lenguaje regular mediante una expresión regular.  Aplicar
el algoritmo de Thompson para pasar de una expresión regular a un autómata
finito.
6. Conocer y 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. Obtener la representación  mínima para cualquier autómata finito
determinista dado.
8. Saber escribir gramáticas libres del contexto que describan entradas
propias de un lenguaje de programación.
9. Construir autómatas de pila que acepten a  lenguajes libres del
contexto  mediante pila vacía y mediante estados finales.
10. Conocer y 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.

Programa

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 Comentario a la equivalencia entre ambas.
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 (descripción).
2.4.2 Un algoritmo de minimización.
2.4.3 Ejemplos.
2.5 Aplicaciones del modelo de autómatas finitos.

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

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.

Actividades

ASIGNATURA EN EXTINCIÓN SIN DOCENCIA.

Distribución de horas de trabajo del alumno

Nº de Horas (indicar total): 87.5

• Clases Teóricas: 30  
• Clases Prácticas: 20  
• Exposiciones y Seminarios:  
• Tutorías Especializadas (presenciales o virtuales):
  • Colectivas:  
  • Individules:  
• Realización de Actividades Académicas Dirigidas:
  • Con presencia del profesor:  
  • Sin presencia del profesor:  
• Otro Trabajo Personal Autónomo:
  • Horas de estudio: 35.5  
  • Preparación de Trabajo Personal:  
  • ...
     
• Realización de Exámenes:
  • Examen escrito: 2  
  • Exámenes orales (control del Trabajo Personal):  

Criterios y Sistemas de Evaluación

CRITERIOS DE EVALUACIÓN

DEL EXÁMENES TEÓRICOS
-El examen teórico se calificará de cero a diez puntos. Se obtiene
Aprobado con una calificación igual o superior a cinco puntos.
-Cada enunciado incluirá la calificación que se le atribuye entre
corchetes.
-Una pregunta teórica o problema se considera correcto únicamente si la
solución que se proporciona es completamente correcta. En otro caso se
considera incorrecta.
-Una pregunta teórica o problema de múltiples apartados se considera
correcto si todos los apartados que lo conforman son correctos. En
cualquier otro caso es incorrecto y no puntúa.

TÉCNICAS DE EVALUACIÓN

Examen Final Teórico de la Asignatura: conteniendo preguntas teóricas
Cortas y/o problemas, con un tiempo de duración nunca superior a las 3
horas.

SISTEMA DE EVALUACIÓN

EVALUACIÓN CON EXAMEN FINAL

La calificación final de la asignatura vendrá determinada por la
calificación obtenida en el examen final.

Recursos Bibliográficos

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.