automatas

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. Objetivos generales . . . . . . . . . . . . . . .
3.2.2. Competencias . . . . . . . . . . . . . . . . . .
3.3. Prerrequisitos . . . . . . . . . . . . . . . . . . . . . .
3.4. Resumen del contenido . . . . . . . . . . . . . . . . .
3.4.1. Descriptor de laasignatura (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
1414

.
.
.
.

15
16
17
18
18

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Dr. Arno Formella

3

5. Conceptos básicos
5.1. Alfabetos . . . . . . . . . . . . . . .
5.2. Palabras . . . . . . . . . . . . . . . .
5.3. Lenguajes . . . . . . . . ....