home

Manual de Autómatas I


INDICE


1. Preliminares
1.1. Conjuntos
1.1.1. Operaciones
1.1.2. Operaciones con conjuntos
1.1.3. Equivalencias de conjuntos
1.1.4. Relaciones y funciones
1.1.5. Conjuntos infinitos
1.2. Manejo lógico de enunciados
1.2.1. Tablas de verdad
1.3. Lenguajes
1.3.1. Alfabeto, cadena de caracteres
1.3.2. Lenguajes, operaciones con lenguajes
1.4. La jerarquía de Chomsky
1.5. Ejercicios
1.6. Resolución de ejercicios

Lenguajes regulares y sus máquinas

2. Autómatas finitos
2.1. Modelado de sistemas discretos
2.1.1. Estados finales
2.2. Máquinas de estados finitos
2.2.1. Funcionamiento de los autómatas finitos
2.3. Definición formal de autómatas finitos
2.4. Métodos de diseño de AFDs
2.4.1. Diseño por conjuntos de estados
2.4.2. Diseño de AFD por complemento
2.5. Equivalencia de autómatas finitos
2.6. Simplificación de Autómatas finitos
2.6.1. Tabla de estados distinguibles
2.6.2. Simplificación por clases de equivalencia
2.7. Autómatas finitos con salida
2.7.1. Máquinas de Moore
2.7.2. Máquinas de Mealy
2.7.3. Equivalencia de las máquinas de Moore y Mealy
2.7.4. Cálculo de funciones en AF
2.8. Autómatas finitos no deterministas
2.8.1. Representación formal de los AFN
2.8.2. Diseño de AFN
2.8.3. Equivalencia de AFD Y AFN
2.8.4. Más diseño de AFN: Intersección de lenguajes
2.9. Ejercicios

3. Expresiones Regulares y Gramáticas Regulares

3.1 Lenguajes Regulares
3.1.1. Definición formal de Lenguajes Regulares
3.2. Expresiones regulares
3.2.1. Significado de las ER
3.2.2. Metodología de diseño de las ER
3.2.3. Equivalencias de Expresiones Regulares
3.3. Límites de las representaciones textuales
3.4. Equivalencia de expresiones regulares y autómatas finitos
3.4.1. Conversión de ER a AF
3.4.2. Conversión de AF a ER
3.5. Gramáticas regulares
3.5.1. Gramáticas formales
3.5.2. Gramáticas regulares
3.5.3. Autómatas finitos y gramáticas regulares
3.6. Limitaciones de los lenguajes regulares
3.6.1. El teorema de bombeo
3.7. Ejercicios
4.. Ayuda
5. Créditos