Teoria de automatas

Teor´ de Aut´matas, ıa o Lenguajes Formales y Gram´ticas a
David Castro Esteban

Copyright c 2003–2004 David Castro Esteban. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-CoverTexts. A copy of the license is included in the section entitled ”GNU Free Documentation License”.

This is as near, I take it, as a finite mind can ever come to “perceiving everything that is happening everywhere in the universe”. The Doors of Perception Aldous Huxley

´ Indice general
Introducci´n o 1

1. Aut´matas finitos o 3 1.1. Aut´matas finitos deterministas . . . . . . . . . . . . .. . . . 3 o 1.2. Aut´matas finitos no deterministas . . . . . . . . . . . . . . . 5 o 1.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2. Gram´ticas regulares a 2.1. Expresiones y gram´ticas regulares . . . a 2.2. Aut´matas finitos y gram´ticas regulares o a 2.3. Aut´matas finitos y expresiones regulares o 2.4. Ejercicios . . . . . . . . . . . . . . . . . 3. Propiedades delos lenguajes regulares 3.1. Lenguajes no regulares . . . . . . . . . 3.2. Propiedades de clausura . . . . . . . . 3.3. Propiedades de decisi´n . . . . . . . . o 3.4. Equivalencia y minimizaci´n . . . . . . o 3.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 15 18 19 22 25 25 27 30 32 38

4. Aut´matas a pila o 41 4.1. Aut´matas a pila . . . . . . . . . . . . . . . . . . . . . . . . . 41 o 4.2. Aut´matas a pila deterministas . . . . . . . . . . . . . . . . . 44 o 4.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5. Gram´ticasindependientes del contexto a 5.1. Gram´ticas independientes del contexto . . . . . . . . . . . a ´ 5.2. Arboles de derivaci´n . . . . . . . . . . . . . . . . . . . . . o 5.3. Aut´matas a pila y gram´ticas independientes del contexto o a 5.4. Ambiguedad en gram´ticas y lenguajes . . . . . . . . . . . a 5.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . i . . . . . . . . . . 47 47 50 54 5757

ii

´ INDICE GENERAL 59 59 67 70 70 72 75 75 76 79 80 80 81 85 85 87 90 90 93 94 96 97 98 99 99 101 102

6. M´quinas de Turing a 6.1. M´quinas de Turing . . . . . . . . . . . . . . . . . . . . . . . a 6.2. M´quinas de Turing no deterministas y con m´ ltiples cintas a u 6.3. Introducci´n a la Ter´ de la Complejidad . . . . . . . . . . o ıa 6.3.1. Tiempo y espacio . . . . . . . . . . . . .. . . . . . . 6.3.2. Resultados b´sicos . . . . . . . . . . . . . . . . . . . a 6.3.3. La conjetura de Cook . . . . . . . . . . . . . . . . . . 6.4. La Tesis de Church–Turing . . . . . . . . . . . . . . . . . . . 6.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

7. Gram´ticas sensibles al contexto y generales a 7.1. Gram´ticas no restringidas ogenerales . . . . . . . . . . . . . a 7.1.1. Definiciones b´sicas . . . . . . . . . . . . . . . . . . . . a 7.1.2. Gram´ticas generales y m´quinas de Turing . . . . . . a a 7.2. Gram´ticas sensibles al contexto . . . . . . . . . . . . . . . . . a a o 7.2.1. Gram´ticas sensibles al contexto y aut´matas linealmente acotados . . . . . . . . . . . . . . . . . . . . . . 7.2.2. Gram´ticas sensibles al contexto ylenguajes recursivos a 7.3. La jerarqu´ de Chomsky . . . . . . . . . . . . . . . . . . . . . ıa 7.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8. Computabilidad 8.1. Propiedades b´sicas . . . . . . . . . . . . . . . . . . . . . . . a 8.2. Lenguajes no recursivamente enumerables . . . . . . . . . . 8.2.1. Codificaci´n de m´quinas de Turing . . . . . . . . . . o a 8.2.2....