Capítulo 1 |
Conceptos básicos |
- Notación de Conjuntos, Funciones, Relaciones
- Sistemas de numeración y aritmética binaria
- Concepto de alfabeto, cadena (string) y lenguaje
- Representación de números en punto flotante
|
Capítulo 2 |
Autómatas finitos |
- Lenguajes formales, definición, propiedades y usos.
- Autómatas Finitos definición y propiedades
- Autómatas finitos determinísticos definición y propiedades
- Autómatas finitos no determinísticos definición y propiedades
- Conversión AFND a AFD
|
Capítulo 3 |
Lenguajes y expresiones regulares |
- Lenguajes regulares definición.
- Propiedades de los lenguajes regulares
- Expresiones regulares definición
- Propiedades de las expresiones regulares
- Conexión entre lenguajes y expresiones regulares
|
Capítulo 4 |
Gramáticas regulares |
- Definición y propiedades de las gramáticas regulares
- Gramáticas lineal a la derecha
- Gramáticas lineal a la izquierda
- Equivalencia de lenguajes y gramáticas regulares
|
Capítulo 5 |
Lenguajes y gramáticas de libre contexto |
- Lenguajes no regulares
- Gramáticas de contexto libre
- Simplificación de gramáticas de contexto libre
|
Capítulo 6 |
Autómatas Pushdown |
- Definición de autómatas pushdown.
- Autómata pushdown no determinístico
- Autómata pushdown y lenguajes de contexto libre
- Autómata pushdown determinístico
|
Capítulo 7 |
Máquinas de Turing |
- Límites del cálculo algorítmico, decidibilidad y computabilidad, lenguajes recursivamente enumerables
- Introducción a las Máquinas de Turing
- Tesis Church - Turing
- Máquinas de Turing como reconocedores de lenguajes
- Máquinas de Turing como traductores
|