Lenguajes Formales, Autómatas y Computabilidad
De Cuba-Wiki
Esta página es sobre la materia del plan de estudios 2023. Para ver la materia del plan 1993, consultar Teoría de Lenguajes.
Lenguajes Formales, Autómatas y Computabilidad
| Año | Segundo año |
|---|---|
| Carga horaria | 5 horas semanales |
| Correlativas | Algoritmos y Estructuras de Datos |
| Correlativa de | Complejidad Computacional |
Lenguajes Formales, Autómatas y Computabilidad es una materia obligatoria de la Licenciatura en Ciencias de la Computación. Su objetivo es introducir al alumnado en las estructuras de autómatas y los lenguajes que estas estructuras pueden definir, junto con aspectos de computabilidad de problemas.
Programa
- Lenguajes
- Autómatas finitos
- Lema de pumping y clausura para lenguajes regulares
- Expresiones regulares
- Autómatas de pila
- Gramáticas
- Funciones primitivas recursivas
- Funciones computables
- Indecibilidad. Diagonalización.
- Reducciones. Teoremas del Parámetro, de la Recursión y de Rice.
