Profesorado

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

-Clases teóricas.
-Clases prácicas.

Metodología

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 únicamente por los medios electrónicos que la plataforma virtual
de la UCA oferta.
Su realización y entrega es obligatoria.

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 algunos tópicos 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.

Distribución de horas de trabajo del alumno/a

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 profesorado:  
  • Sin presencia del profesorado:  
• 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):  

Técnicas Docentes

Criterios y Sistemas de Evaluación

CRITERIOS DE EVALUACIÓN

A) DE 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.

B) DE EXÁMENES PRÁCTICOS
-Se realizará en ordenador.
-El examen práctico se calificará con APTO O NO APTO. Se obtiene APTO
cuando al menos el 50% de los enunciados del examen son correctos.
-Las condiciones que una solución a un enunciado de examen debe cumplir
para ser considerada correcta son:
a) Los ficheros subifod a través del Campus Virtual que conforman el
examen práctico se ajustan al número,  formato y nomenclatura de nombres
explicitados por el profesor en el documento de examen.
b)El contenido de los ficheros es el especificado por el profesor en el
documento de examen.
c)Para ficheros elaborados con JFLAP (en su caso), se pueden abrir y
procesar con el software citado, y realizan un procesamiento técnicamente
correcto,según el enunciado de que se trate.
d)Para ficheros elaborados en lenguaje C (en su caso), la compilación y
ejecución son correctas, y el procesamiento es técnicamente correcto,
según el enunciado de que se trate.

C)DE TRABAJOS PUNTUABLES
-Deberá entregarse en tiempo y forma.
-Deberá desarrollarse siguiendo las especificaciones hechas públicas por
el profesor.
-Los contenidos teóricos que recoja serán correctas de acuerdo al estado
actual de la materia.
-Lo problemas estarán bien desarrollados.

TÉCNICAS DE EVALUACIÓN POSIBLES

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

b)Examen Final de Prácticas: contendrá enunciados similares a los
desarrollados durante las prácticas de la asignatura 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 a través del campus
virtual. Su duración no será mayor de 90 minutos. No se permitirá el uso
de material alguno durante su realización.Si se cumplen los requisitos
establecidos de entrega de prácticas y asistencia
a clases prácticas se obtendrá la calificación de APTO en prácticas, no
siendo necesaria la realización del examen práctico.

c) Asistencia y Participación
Aplicable únicamente bajo evaluación continua, el alumno deberá acreditar
una asistencia a clases teóricas y prácticas de al menos el 80%, y
realizar aportaciones objetivables y cuantificables al foro, glosario y
wiki de la asignatura.

d) Trabajo Final Dirigido
Aplicable únicamente bajo evaluación continua, el alumno deberá
desarrollar un trabajo por escrito sobre la materia de acuerdo a los
contenidos y especificaciones hechos públicos por el profesor.

SISTEMA DE EVALUACIÓN

1) EVALUACIÓN CONTINUA
Se desarrollará bajo los siguiente criterios:
a) Asistencia a clases teóricas y prácticas de al menos el 80%
b) Entrega obligatoria de todas las prácticas de la asignatura
c) Entrega de una memoria de teoría y problemas
d) La asistencia y participación permite obtener hasta 4 puntos.
e) La memoria de teoría y problemas permite obtener hasta 6 puntos.
f) Es necesario obtener APTO en prácticas.
g) La calificación final es la suma de las obtenidas en los apartados d) y
e) anteriores, habiendo obtenido APTO en prácticas.
h) Será el modelo de evaluación por aplicable por defecto a todos los
alumnos.

2) EVALUACIÓN ORDINARIA CON EXAMEN FINAL

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

b)El examen final práctico no será corregido si no se supera el examen
final teórico.

c)Aquél alumno que obtenga NO APTO (menos del 50% de enunciados resueltos
correctamente) en el examen práctico pero supere el 30% podrá compensar la
diferencia y obtener APTO mediante las asignaciones de prácticas que se
habrán ido entregando durante el curso con carácter obligatorio, siempre
que se cumpla el siguiente criterio: todas ellas hayan sido entregadas y
al menos el 70% de las mismas estén bien resueltas.

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
indispensable para obtener APTO en las prácticas de la asignatura en ambas
modalidades de evaluación. En caso de enfermedad o fuerza mayor
documentalmente justificadas, el profesor indicará al alumno nueva fecha
de entrega.

2)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 llamamientos y días de revisión de calificaciones se refiere.

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

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

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.