Lenguaje Formales y Autómatas

Unidad 1 - Introducción a los lenguajes formales

Concepto de símbolo, alfabeto, cadena y lenguaje. Operaciones entre cadenas y lenguajes. Propiedades.

Teoría: T1_Lenguajes.pdf

Prácticas: Practico0.pdf (esta es un repaso de los concepto de la teoría de conjuntos), Practico1.pdf

Unidad 2 - Lenguajes regulares y Autómata finitos

Autómata finito: definiciones básicas; diagrama de transición; ejemplos. Autómata finito determinístico: reconocimiento y traducción. Autómata finito no determinístico. Equivalencia de autómata finito determinístico y no determinístico. Minimización de autómatas. Autómatas Traductores. Lenguajes regulares. Gramáticas regulares. Expresiones regulares. Equivalencia entre gramáticas y expresiones regulares. Leyes algebraicas de expresiones regulares. Equivalencia de expresiones regulares y autómatas finitos. Propiedades de clausura de los lenguajes regulares. Lema de Bombeo para lenguajes regulares.

Teoría: T2_Leng-GramyExpRegulares.pdf, T3_AutomatasFinitosyTraductores.pdf

Prácticas: Practico2.pdf, Practico3.pdf

Unidad 3 - Autómata con pila y lenguajes libres del contexto

Autómata con pila: definiciones básicas; diagrama de transición; ejemplos. Autómata con pila determinístico: reconocimiento y traducción. Autómata con pila no determinístico. Lenguajes libres del contexto. Gramáticas libres de contexto. Equivalencia entre gramáticas libres de contexto y autómatas con pila. Ambigüedad. BNF (Backus Naur Form). Base gramatical de la traducción de lenguajes.

Teoría: T4_GLC.pdf , T5_AutomatasConPila.pdf

Práctico: Practico4.pdf, Practico5.pdf

Unidad 4 - Máquina de Turing

Máquina de Turing: definiciones básicas; ejemplos. Máquina de Turing determinística: reconocimiento y traducción. Máquina de Turing multicinta. Máquina de Turing no determinística. Autómata linealmente acotado y lenguajes sensibles al contexto. Gramáticas sensibles al contexto. Máquina de Turing y lenguajes estructurados por frases. Gramáticas.

Teoría: T6_MaqTuring.pdf

Práctico: T6_MaqTuring.pdf

Unidad 5 - Jerarquía de Chomsky

Jerarquía de Chomsky. Gramáticas de tipo 0, 1, 2 y 3. Relación entre clases de lenguajes. Ejemplos.

Bibliografía

• Hopcroft, J. E.; Motwani, R.; Ullman, J. D. , “Introducción a la teoría de autómatas, lenguajes y computación”. Tercera edición, PEARSON EDUCACIÓN S.A., Madrid, 2007

• Isabel Navarrete Sánchez, et all. “Teoría de Autómatas y Lenguajes Formales“

• Departamento de Ingeniería de la Información y las Comunicaciones. Universidad de Murcia

• Brookshear J. “Teoría de la computación. Lenguajes Formales, Autómatas y Complejidad”. Addison Wesley Iberoamericana, 1993.

• Kelley, D. “Teoría de autómatas y lenguajes formales”. Prentice Hall. 1995

• Lewis, H.; Papadimitriou, C. “Elements of Theory of Computation”. Second Edition. Prentice Hall. 1998.

• Martin, John; “Lenguajes Formales y Teoría de la Computación”. 3ra. Edición. McGraw-Hill. 2004.

• Sipser, Michael. “Introduction to the theory of computation”, second edition. Thomson Course Technology. (2006)

Cronograma de clases