Esta obra abarca los temas de lenguajes formales y autómatas, máquinas de Turing y computabilidad a través de la decibilidad. Su estudio necesita un nivel mínimo de conocimientos matemáticos aunque se eviten en lo posible los largos desarrollos matemáticos. Todos los razonamientos de este libro tienen la intención de motivar al alumno, más que pretender ser matemáticamente completos o elegantes. En todo momento el autor ilustra con ejercicios y problemas de dificultad diversa los conceptos que expone a lo largo de esta obra.
Contenido:
Prologo
0. Preliminares matemáticos
0.1. Lógica elemental
0.2. Definiciones básicas
0.3. Definiciones con conjuntos
0.4. Relaciones y funciones
0.5. Inducción
0.6. Cardinalidad
1. Alfabetos y lenguajes
1.1. Alfabetos, palabras y lenguajes
1.2. Operaciones con cadenas
1.3. Operaciones con lenguajes
Problemas
2. Lenguajes regulares
2.1. Lenguaje sobre alfabetos
2.2. Lenguajes regulares y expresiones regulares
2.3. Autómata finito determinista
2.4. AFD y lenguajes
2.5. Autómata finito no determinista
2.6. Equivalencia de AFN y AFD
2.7. E-transiciones
2.8. Autómata finito y expresiones regulares
2.9. Propiedades de los lenguajes regulares
2.10. Aplicaciones de las expresiones regulares y los autómatas finitos
Problemas
3. Lenguajes independientes del contexto
3.1. Gramáticas regulares
3.2. Gramáticas regulares y lenguajes regulares
3.3. Gramáticas independientes del contexto
3.4. Árboles de derivaron o de análisis y ambigüedad
3.5. Simplificación de gramáticas independientes del contexto
3.6. Propiedades de los lenguajes independientes del contexto
3.7. Autómata de pila
3.8. Autómata de pila y lenguajes independientes del contexto
3.9. Forma normal de Greibach
No hay comentarios:
Publicar un comentario