Lenguajes y Autómatas - Módulo 1.2 (Jerarquía de Chomsky)

Material elaborado por el Profesor Dr. Fabián Riquelme Csori, para el curso de Lenguajes y Autómatas, de la Escuela de Ingeniería Civil Informática de la Universidad de Valparaíso, Chile.

MÓDULOS DEL CURSO
Capítulo 1. Lenguajes regulares y autómatas finitos.
1. Alfabetos, cadenas y lenguajes
2. Jerarquía de Chomsky
3. Expresiones regulares
4. Autómatas finitos deterministas (DFA)
5. Autómatas finitos no-deterministas (NFA)
6. Conversión y equivalencia NFA-DFA
7. Lema del bombeo (para lenguajes regulares)

Capítulo 2. Lenguajes libres de contexto y autómatas de pila
1. Gramáticas libres de contexto (CFG)
2. Árboles de derivación
3. Autómatas de pila (PDA)
4. Conversión CFG-PDA
5. Lema del bombeo (para lenguajes libres de contexto)

Capítulo 3. Máquinas de Turing y computabilidad
1. Tesis de Church-Turing
2. Máquinas de Turing (TM)
3. TM en notación modular
4. Variaciones de TM
5. TM no-deterministas