LF

Teoría de Autómatas y Lenguajes Formales
Versión 11
Dr. Arno Formella
Universidade de Vigo
Escola Superior de Enxeñaría Informática
Departamento de Informática
Área de Linguaxes e Sistemas Informáticos
E-32004 Ourense
http://www.ei.uvigo.es/˜formella
formella@ei.uvigo.es

Junio 2010

Dr. Arno Formella

2

Índice
1. Curso
1.1. Administración . . . . . . . . .
1.2. Clases . . . . . . . . . . . . ..
1.3. Tutorías . . . . . . . . . . . . .
1.4. Evaluación . . . . . . . . . . .
1.4.1. Asistentes y no asistentes
1.4.2. Entregas . . . . . . . . .
1.5. Exámenes . . . . . . . . . . . .

.
.
.
.
.
.
.

5
5
5
5
5
5
6
7

2. Sobre este documento
2.1. Versiones y lista de correcciones . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

3. Guía docente
3.1. Contextualización . . . . . . . . . . . . . . . . . . . .
3.1.1. Perfil de los créditos de la asignatura . . . . . .
3.1.2. Ubicación y relación con el Plan de Estudios .
3.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Objetivosgenerales . . . . . . . . . . . . . . .
3.2.2. Competencias . . . . . . . . . . . . . . . . . .
3.3. Prerrequisitos . . . . . . . . . . . . . . . . . . . . . .
3.4. Resumen del contenido . . . . . . . . . . . . . . . . .
3.4.1. Descriptor de la asignatura (BOE) . . . . . . .
3.4.2. Teoría . . . . . . . . . . . . . . . . . . . . . .
3.4.3. Práctica . . . . . . . . . . . . . . . . . . . . .
3.5.Metodologías y estrategias de aprendizaje . . . . . . .
3.6. Plan de trabajo del alumnado presencial . . . . . . . .
3.7. Evaluación de los procesos y resultados de aprendizaje.
Criterios de evaluación . . . . . . . . . . . . . . . . .
3.7.1. Criterios de evaluación para asistentes . . . . .
3.7.2. Criterios de evaluación para no asistentes . . .
3.8. Observaciones . . . . . . . . . . . . . . . . . . . . ..
4. Introducción
4.1. Reglas de sustitución para formar secuencias
4.2. Autómatas que aceptan secuencias . . . . . .
4.3. Lenguajes y autómatas . . . . . . . . . . . .
4.4. Máquinas de Turing universales . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
..
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

10
10
10
10
10
10
11
12
12
12
12
12
13
13

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

13
13
14
14

.
.
.
.

15
16
17
18
18

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Dr. Arno Formella

3

5. Conceptosbásicos
5.1. Alfabetos . . . . . . . . . . . . . . .
5.2. Palabras . . . . . . . . . . . . . . . .
5.3. Lenguajes . . . . . . . . . . . . . . .
5.4. Producciones y Derivaciones . . . . .
5.5. Relaciones de equivalencia . . . . . .
5.6. Relación de equivalencia de lenguajes
6. Gramáticas generativas
6.1. Ejemplos . . . . . . . . .
6.2. Abreviación de Backus . .
6.3. Árbol de derivación . . . .
6.4.Jerarquia de Chomsky . . .
6.5. Equivalencia y ambigüedad

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

7. Autómatas finitos
7.1. Autómatas finitos deterministas (AFD) . . . . . . . ....