Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 2013) 2024-2

Cuarto Semestre, Autómatas y Lenguajes Formales

Grupo 7060, 40 lugares. 40 alumnos.
Profesor Víctor Germán Mijangos de la Cruz lu mi vi 12 a 13 T1
Ayudante Teresa Becerril Torres ma ju 12 a 13 T1

 

Presentación del curso: Este curso es una introducción a los conceptos de autómatas, y a la teoría del lenguajes formales. Se tratarán los diferentes tipos de lenguajes, sus gramáticas y los autómatas asociados. Asimismo, se expondrán las propiedades de éstos y las capacidades de estos modelos para trabajar problemas de cómputo.

Forma de evaluación: El curso consistirá de 4 o 3 exámenes y de tareas relacionadas. El porcentaje de la calificación será:

Concpeto Porcentaje
Exámenes 60 %
Tareas 40 %

Temario

  1. Introducción

    1. Motivación

    2. Marco histórico

    3. Alfabetos, cadenas y lenguajes

    4. Gramáticas formales

  2. Lenguajes regulares

    1. Expresiones regulares

    2. Definición de lenguaje regular

    3. Propiedades de lenguajes regulares

    4. Representaciones de lenguajes regulares

  3. Autómatas finitos

    1. Definición de autómata finito

    2. Autómata finito determinista, no determinista y con transiciones epsilon

    3. Lenguajes regulares y autómatas finitos

    4. Transformación entre representaciones

    5. Equivalencia y minimización

    6. Lema del bombeo

  4. Lenguajes libres de contexto

    1. Definición de lenguaje libre de contexto

    2. Propiedades de lenguajes libres de contexto

    3. Derivaciones y representaciones árboreas

    4. Forma normal estándar

    5. Forma normal de Chomsky

    6. Forma normal de Greibach

  5. Autómatas con pila

    1. Definición y propiedades

    2. Lenguajes libres de contexto y autómatas con pila

    3. Configuraciones

    4. Lema del bombeo y lema de Ogden

    5. Decibilidad

  6. Máquinas de Turing

    1. Definición de máquina de Turing

    2. Construcción de máquinas de Turing

    3. Máquina de Turing Universal

    4. Tesis Church-Turing

    5. Lenguajes recursivamente enumerables y jerarquía de Chomsky

  7. Introducción a la decibilidad

    1. Indecibilidad

    2. Problema de la detención (Halting problem)

    3. Reducción y decibilidad

    4. Funciones computables

Bibliografía

Viso G., E. (2008), Introducción a la teoría de la computación. México: Las Prensas de Ciencias.

Ullman, J. y Hopcroft, J. (2006). Introduction to Automata Theory, Languages, and Computation. Prentice Hall.

Rich, E. (2019). Automata, computability and complexity: Theory and Applications. Pearson Education.

Link de classroom

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.