Gua De Automatas

GUÍA INTEGRADORA DE ACTIVIDADES

Autómatas y lenguaje s Formales_ 301405

Temáticas revisadas: Exploración de las referencias requeridas y referencias complementarias de cada una

de las unidades que conforma el curso.

Unidad 1: Lenguajes Regulares.

- Introducción e Historia

- Alfabetos, cadenas y lenguajes

- Autómatas y lenguajes

- Lenguajes Regulares

- Autómata

- Definición formal de autómatas finitos

- Autómatas finitos determinísticos (AFD)

- Autómatas finitos No determinísticos (AFND)

- Autómatas finitos con transiciones 

- Lenguaje aceptado por un autómata finito

- Lenguajes regulares y Expresiones Regulares

- Significado de la Expresiones Regulares

- Autómatas finitos y Expresiones Regulares

- Equivalencia de AFD y de AFND

- Minimización de autómatas

Unidad 2: Lenguajes Independientes del contexto

- Gramáticas Regulares

- Lenguajes libres de contexto y sus máquinas

- Arboles de derivación

- Trasformación de las GLC y Formas Normales

- Limitaciones de los LLC

- Definición de Autómata con Pila

- Funcionamiento de un PDA

- Diseño de un PDA

- Funciones que se aplican sobre los stacks (Pilas)

- Combinación modular de los Autómatas con Pila

- Lenguaje aceptado por un PDA

- Relación entre los AP y los LLC

- Propiedades de clausura de los LLC

- Algoritmos de decisión para los LLC

- Problemas indecidibles para los LLC

Unidad 3: Lenguajes estructurados pro frases.

- Formalización de las Máquinas de Turing (MT)

- Funcionamiento de las MT

- Diferencias entre un computador y una MT

- La Máquina Universal de Turing (MUT)

- Lenguajes aceptados por la MT

- Tesis de Church/Turing

- Variantes de una MT

- Problemas de Hilbert

- Problemas Insolubles para la Teoría de Lenguajes

- Lenguajes Decidibles

-

...