apuntes de Algoritmos

Cuadernillo de apuntes Teor´ de la
ıa
computaci´n
o
Magaly Gonz´lez Mota
a
30 de junio de 2010

2

´
Indice general
1. INTRODUCCION
1.1. Aut´matas computabilidad y complejidad
o
1.1.1. Representaciones estructurales . . .
1.1.2. Aut´matas y la complejidad . . . .
o
1.2. Nociones Matem´ticas . . . . . . . . . . .
a
1.2.1. Conjuntos . . . . . . . . . . . . . .
1.2.2.Funciones y relaciones . . . . . . .
1.2.3. Inducci´n matem´tica . . . . . . .
o
a
1.3. Cadenas y lenguajes . . . . . . . . . . . .
2. Lenguajes regulares
2.1. Aut´matas finitos . . . .
o
2.1.1. Aut´matas finitos
o
2.1.2. Aut´matas finitos
o
2.2. Expresiones regulares . .
2.3. Lenguajes Regulares . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
..
.
.

.
.
.
.
.
.
.
.

. . . . . . . . . . . . . . .
deterministicos AFD . . .
no deterministicos AFND
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .

3. Lenguajes libres de contexto
3.1. Gram´ticas libres de contexto
a
´
3.2. Arboles de derivaci´n . . . . .
o
3.3. Formas normales de Comsky .
3.4. Forma normal de Greibach . .
3.5. Ambig¨edad . . . . . . . .. .
u
3.6. Aut´matas de Pila . . . . . .
o
3.7. Lenguajes no regulales . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
..

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

5
5
7
7
7
7
12
17
19

.
.
.
.
.

25
25
26
29
31
35

.
..
.
.
.
.

37
37
41
45
45
46
47
55

4. M´quinas de Turing
a
61
4.1. Definici´n de una M´quina de Turing . . . . . . . . . . . . . . 63
o
a
3

´
INDICE GENERAL

4
4.2. Construcci´n modular de una MT . . . . . .
o
4.3. El lenguaje de una M´quina de Turing . . .
a
4.4. Variantes de una M´quina de Turing . . . .
a
4.4.1. M´quina de Turing con varias cintas
a
4.4.2.M´quinas con pilas multiples . . . .
a
4.4.3. M´quinas contadoras . . . . . . . . .
a

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

66
70
71
71
72
73

5. Decibilidad
5.1. Lenguajes Decidibles . . . . . . . . . . . . . . . . . . . . . . .
5.2. El problema de Halting . . . . . . . . . . . . . . . . . . . . . .
5.3. Decibilidad de teor´ l´gicas . . . .. . . . . . . . . . . . . . .
ıas o

77
78
79
80

6. Reducibilidad
6.1. Problemas insolubles para la teor´ de lenguajes
ıa
6.2. Un problema simple insoluble . . . . . . . . . .
6.2.1. Algoritmo de Kruskal . . . . . . . . . . .
6.3. Funciones computables . . . . . . . . . . . . . .

83
83
85
85
88

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
..
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.

Cap´
ıtulo 1
INTRODUCCION
Objetivo de la Unidad
Situar la importancia del estudio de los
aut´matas dentro del proceso de desarrollo de software, y algunas aplicao
ciones. Presentar las nociones b´sicas de matem´ticas necesarias para comenaa
zar a estudiar la materia.

1.1.

Aut´matas computabilidad y complejio
dad

Se conoce como teor´a de aut´matas el estudio de las m´quinas o disposı
o
a
itivos abstractos con capacidad de computaci´n.
o
En la decada de 1930 el matem´tico ingles Alan Mathison Turing estudi´ una
a
o
m´quina con el objetivo de determinar con presici´n cu´l era la frontera entre
a
o
a
lo que...