Analista de sistemas

Modelos de Computación I
Serafín Moral Departamento de Ciencias de la Computación e I.A. ETSI Informática Universidad de Granada

2

Modelos de Computación I

Í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 27 33 34 37 39 42 43 46 47 51 59 63 63 65 66 69 70 74 76

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

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

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

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

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

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

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áquinas deMealy . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.3. Equivalencia de Máquinas de Mealy y Máquinas de Moore . . . .

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 . . . . . .. . . . . . . . . . . 3

4

Modelos de Computación I 3.4. Teorema de Myhill-Nerode. Minimización de Autómatas . . . . . . . . . . . . 3.4.1. Minimización de Autómatas . . . . . . . . . . . . . . . . . . . . . . . 77 81 87 88 91 92 95 97 98 98 99

4. Gramáticas Libres de Contexto 4.1. Arbol de Derivación y Ambigüedad . . . . . . . . . . . 4.2. Simplificación De Las Gramáticas Libres DeContexto . 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 . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . ..

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

5. Autómatas con Pila 105 5.1. Definición de Autómata con Pila . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.2. Autómatas con Pila y Lenguajes Libres de Contexto . . . . . . . . . . . . . . . 108 6. Propiedades delos Lenguajes Libres del Contexto 6.1. Lema de Bombeo . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Propiedades de Clausura de los Lenguajes Libres de Contexto . . 6.3. Algoritmos de Decisión para los Lenguajes Libres de Contexto . . 6.3.1. Algoritmos de Pertenencia . . . . . . . . . . . . . . . . . 6.3.2. Problemas Indecidibles para Lenguajes Libres de Contexto . . . . . . . . . . ....