Encabezado Facultad de Ciencias
Presentación

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

Cuarto Semestre, Autómatas y Lenguajes Formales

Grupo 7060, 50 lugares. 50 alumnos.
Profesor Víctor Germán Mijangos de la Cruz lu mi vi 10 a 11
Ayudante Teresa Becerril Torres ma ju 10 a 11

 

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 3 exámenes y de tareas. El porcentaje de la calificación será:

Concpeto Porcentaje
Exámenes 40 %
Tareas 60 %

La calificación final dependerá de la realización de los 3 exámenes.


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. Lema del bombeo

    5. Transformación entre representaciones

    6. Equivalencia y minimización

  4. Lenguajes libres de contexto

    1. Definición de lenguaje libre de contexto

    2. Propiedades de lenguajes libres de contexto

    3. Forma normal estándar

    4. Forma normal de chomsky y algoritmo CYK

    5. 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. Lema de Ogden

    4. 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

Classroom: https://classroom.google.com/c/NTg1OTk1NzUyODgw?cjc=wghfzz7

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.

 


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.