publicidad

Teoría de Autómatas y Lenguajes Formales
Serafín Moral
Departamento de Ciencias de la Computación e I.A.
ETSI Informática
Universidad de Granada

2

Teoría de Autómatas y Lenguajes Formales

Índice general
1. Introducción
1.1. Introducción Histórica . . . . . . . . . . . . . . .
1.2. Diferentes Modelos de Computación . . . . . . . .
1.2.1. Autómatas y Lenguajes . . . . . . . . . ..
1.3. Lenguajes y Gramáticas. Aspectos de su traducción
1.3.1. Alfabetos y Palabras . . . . . . . . . . . .
1.3.2. Lenguajes . . . . . . . . . . . . . . . . . .
1.3.3. Gramáticas Generativas . . . . . . . . . .
1.3.4. Jerarquía de Chomsky . . . . . . . . . . .

.
.
.
.
.
.
.
.

5
7
11
15
17
17
19
22
25

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

29
30
32
33
35
37
3940
44
52
56
57
58
59

3. Propiedades de los Conjuntos Regulares
3.1. Lema de Bombeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Operaciones con Conjuntos Regulares . . . . . . . . . . . . . . . . . . . . . .
3.3. Algoritmos de Decision para Autómatas Finitos . . . . . . . . . . . . . . . . .

63
64
67
69

.
.
.
.
.
.
.
.

.
.
.
.
.
.
..

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

2. Autómatas Finitos, Expresiones Regulares y Gramáticas de tipo 3
2.1. Autómatas Finitos Determinísticos . . . . . . . . . . . . . .. . . . . . .
2.1.1. Proceso de cá lculo asociado a un Autómata de Estado Finito . . .
2.1.2. Lenguaje aceptado por un Autómata de Estado Finito . . . . . . .
2.2. Autómatas Finitos No-Determinísticos (AFND) . . . . . . . . . . . . . .
2.2.1. Diagramas de Transición . . . . . . . . . . . . . . . . . . . . .
2.2.2. Equivalencia de Autómatas Determinísticos y No-Determinísticos
2.3. AutómatasFinitos No Deterministicos con transiciones nulas . . . . . .
2.4. Expresiones Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Gramáticas Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6. Máquinas de Estado Finito . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.1. Máquinas de Moore . . . . . . . . . . . . . . . . . . . . . . . .
2.6.2. Máquinasde Mealy . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.3. Equivalencia de Máquinas de Mealy y Máquinas de Moore . . . .

3

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

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

4

Teoría de Autómatas y Lenguajes Formales
3.4. Teorema de Myhill-Nerode. Minimización de Autómatas . . . . . . . . . . . .3.4.1. Minimización de Autómatas . . . . . . . . . . . . . . . . . . . . . . .

4. Gramáticas Libres de Contexto
4.1. Arbol de Derivación y Ambigüedad . . . . . . . . . . .
4.2. Simplificación De Las Gramáticas Libres De Contexto .
4.2.1. Eliminación de Símbolos y Producciones Inútiles
4.2.2. Producciones Nulas . . . . . . . . . . . . . . . .
4.2.3. Producciones Unitarias . . . . . . . . . . .. . .
4.3. Formas Normales . . . . . . . . . . . . . . . . . . . . .
4.3.1. Forma Normal de Chomsky . . . . . . . . . . .
4.3.2. Forma Normal de Greibach . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
..
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

70
74
81
82
85
86
89
91
92
92
93

5. Autómatas con Pila
99
5.1. Definición de Autómata con Pila . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2. Autómatas con Pila y Lenguajes Libres de Contexto . . . . . . . . . . . . . . . 102
6. Propiedades de los Lenguajes Libres del...