Menu Content/Inhalt
Home
Lenguajes Formales y Computabilidad

Contenidos Mínimos:

  1. Autómatas finitos y lenguajes regulares (Teorema de Kleene).
  2. Gramáticas regulares y libres de contexto.
  3. Forma normal de Chomsky.
  4. Autómatas a pila y lenguajes libres de contexto.
  5. Máquinas de Turing.
  6. Lenguaje de programación para funciones recursivas.
  7. Funciones parcialmente computables.
  8. Tesis de Church.
  9. El halting problem.
  10. Programas universales.
  11. Teoremas del parámetro, de la recursión y de Rice.
  12. Forma normal de Kleene de una función parcialmente computable.
  13. Conjuntos r.e.
  14. Lenguajes r.e.
  15. Funciones parcialmente computables sobre palabras.
  16. Equivalencia entre las funciones recursivas parciales, funciones Turing computables y funciones parcialmente computables.
  17. Jerarquía de Chomsky.

Bibliografía:

  1. J.E. HOPCROFT & J.D. ULLMAN, Introduction to automata theory languages and computation, Addison-Weasley, Reading, Mass., 1979.
  2. I. SIMON, Linguagens formais e automatos, Segunda escola de computaçao, Instituto de Matemática, Estatística e Ciencia da Computaçao da UNICAMP, Campinas, 1981.
  3. R. HARTLEY, Theory of Recursive Functions and Effective Computability, McGraw-Hill Series in Higher Mathematics.
  4. M. DAVIS & E. WEYUKER. Computability, Complexity and Languages. Academic Press. 1986.
 
< Anterior   Siguiente >
Content Management System: Joomla!
Template based on an original designed by www.madeyourweb.com