Automata

130 pages
64 views
of 130
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Automata
Tags
Transcript
  Modelos de Computación I Serafín MoralDepartamento de Ciencias de la Computación e I.A.ETSI InformáticaUniversidad de Granada  2 Modelos de Computación I  Índice general 1. Introducción 5 1.1. Introducción Histórica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2. Diferentes Modelos de Computación . . . . . . . . . . . . . . . . . . . . . . . 111.2.1. Autómatas y Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3. Lenguajes y Gramáticas. Aspectos de su traducción . . . . . . . . . . . . . . . 171.3.1. Alfabetos y Palabras . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.3.2. Lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.3.3. Gramáticas Generativas . . . . . . . . . . . . . . . . . . . . . . . . . 221.3.4. Jerarquía de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2. Autómatas Finitos, Expresiones Regulares y Gramáticas de tipo 3 33 2.1. Autómatas Finitos Determinísticos . . . . . . . . . . . . . . . . . . . . . . . . 342.1.1. Proceso de cá lculo asociado a un Autómata de Estado Finito . . . . . . 372.1.2. Lenguaje aceptado por un Autómata de Estado Finito . . . . . . . . . . 392.2. Autómatas Finitos No-Determinísticos (AFND) . . . . . . . . . . . . . . . . . 422.2.1. Diagramas de Transición . . . . . . . . . . . . . . . . . . . . . . . . 442.2.2. Equivalencia de Autómatas Determinísticos y No-Determinísticos . . . 452.3. Autómatas Finitos No Deterministicos con transiciones nulas . . . . . . . . . 482.4. Expresiones Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522.4.1. Propiedades de las Expresiones Regulares . . . . . . . . . . . . . . . . 532.4.2. Expresiones Regulares y Autómatas Finitos . . . . . . . . . . . . . . . 542.5. Gramáticas Regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612.6. Máquinas de Estado Finito . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652.6.1. Máquinas de Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . 652.6.2. Máquinas de Mealy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672.6.3. Equivalencia de Máquinas de Mealy y Máquinas de Moore . . . . . . . 68 3. Propiedades de los Conjuntos Regulares 71 3.1. Lema de Bombeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723  4 Modelos de Computación I3.2. Operaciones con Conjuntos Regulares . . . . . . . . . . . . . . . . . . . . . . 763.3. Algoritmos de Decision para Autómatas Finitos . . . . . . . . . . . . . . . . . 783.4. Teorema de Myhill-Nerode. Minimización de Autómatas . . . . . . . . . . . . 793.4.1. Minimización de Autómatas . . . . . . . . . . . . . . . . . . . . . . . 83 4. Gramáticas Libres de Contexto 89 4.1. Arbol de Derivación y Ambigüedad . . . . . . . . . . . . . . . . . . . . . . . 904.2. Simplificación De Las Gramáticas Libres De Contexto . . . . . . . . . . . . . 934.2.1. Eliminación de Símbolos y Producciones Inútiles . . . . . . . . . . . . 944.2.2. Producciones Nulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.2.3. Producciones Unitarias . . . . . . . . . . . . . . . . . . . . . . . . . . 994.3. Formas Normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.3.1. Forma Normal de Chomsky . . . . . . . . . . . . . . . . . . . . . . . 1014.3.2. Forma Normal de Greibach . . . . . . . . . . . . . . . . . . . . . . . 102 5. Autómatas con Pila 107 5.1. Definición de Autómata con Pila . . . . . . . . . . . . . . . . . . . . . . . . . 1085.1.1. Lenguaje aceptado por un autómata con pila . . . . . . . . . . . . . . . 1095.2. Autómatas con Pila y Lenguajes Libres de Contexto . . . . . . . . . . . . . . . 1115.3. Lenguajes Independientes del Contexto Deterministas . . . . . . . . . . . . . . 113 6. Propiedades de los Lenguajes Libres del Contexto 117 6.1. Lema de Bombeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186.2. Propiedades de Clausura de los Lenguajes Libres de Contexto . . . . . . . . . 1206.3. Algoritmos de Decisión para los Lenguajes Libres de Contexto . . . . . . . . . 1216.3.1. Algoritmos de Pertenencia . . . . . . . . . . . . . . . . . . . . . . . . 1226.3.2. Problemas Indecidibles para Lenguajes Libres de Contexto . . . . . . . 127  Capítulo 1Introducción 5
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks