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, todo ello 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

Troncal de segundo curso. Establece el cuerpo de conocimientos teóricos mínimo
que permite a los alumnos el seguimiento con garantías de la asignatura
obligatoria de tercer curso "Traductores"

Recomendaciones

Se hacen al alumno las siguientes recomendaciones:

1) Más vale un mal libro que muchos buenos apuntes: por tanto, para cada tema
concreto del curso se le propondrán como material de revisión/trabajo/estudio
un mínimo de dos y un máximo de cuatro capítulos de referencias concretas (en
inglés, claro está). También se le proporcionarán unos apuntes (en
castellano), 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. En particular, la asistencia a clase en un
derecho/deber del alumno; acuda a clase. El profesor llevará un control de la
asistencia del alumno a efectos meramente informativos.

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
El propósito principal del programa práctico es el uso de software de
simulación de máquinas de estados con capacidad de reconocimiento de lenguajes
regulares y libres del contexto. Se escoge el software JFLAP, de libre
distribución y multiplataforma como herramienta de trabajo. También se
realizarán alguna práctica de programación en lenguaje C relacionada con los
contenidos de la asignatura.

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, el cual una vez resuelto, 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 (ver apartado de
evaluación).

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 comprensió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: 15  
• Exposiciones y Seminarios: 0  
• 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: 40.5  
  • Preparación de Trabajo Personal:  
  • ...
     
• Realización de Exámenes:
  • Examen escrito:  
  • Exámenes orales (control del Trabajo Personal):  

Técnicas Docentes

Criterios y Sistemas de Evaluación

CRITERIOS DE EVALUACIÓN

A) DEL EXAMEN TEÓRICO
-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) DEL EXAMEN PRÁCTICO
-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 subidos 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.


TÉCNICAS DE EVALUACIÓN

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. Al
comienzo del mismo, el alumno dispondrá de 15 minutos para realizar las
consultas que estime oportunas sobre sus apuntes y/o material bibliográfico, y
realizar las anotaciones que estime pertinentes. El resto del tiempo de
duración de la prueba transcurrirá sin acceso a material alguno.

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.

SISTEMA DE EVALUACIÓN

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 y se hayan entregado todas las
asignaciones de prácticas. Si superándose el examen teórico no se supera el
examen práctico, la calificación final será de 4 puntos.

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 las asignaciones han 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 OBLIGATORIA. Si se
dejan sin entregar asignaciones sin causa justificada, no podrá
obtenerse APTO en el Examen Final de Prácticas. En caso de no entregar una
asignación por enfermedad o causa de fuerza mayor documentalmente justificadas,
el profesor indicará al alumno nueva fecha de entrega. Para las convocatorias
de Junio y Septiembre, se habilitará un período de entrega de prácticas
atrasadas a los mismos efectos.

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.