Autómatas y lenguajes formales

Virtual Machine

1. ALFABETOS Y LENGUAJES

  • Alfabetos y lenguajes
  • Introducción a Notebook, JFLAP
  • Conceptos Básicos

Pres_0_Intro

Pres_1_Intro

Pres_1_2_Alfab

Python

Notebook_MarkDown_Intro.ipynb

Python

Notebook_Python_Intro.ipynb

Python

Notebook_Python_Intro_extra.ipynb

Python

Notebook_DIccionarios_Funciones_Automatas.ipynb

2. AUTÓMATAS FINITOS

  • Introducción a Autómatas Finitos
  • Autómatas Finitos deterministas
  • Autómatas Finitos No deterministas
  • Autómatas Finitos con transiciones ε




Pres_2_1_AFD

Pres_2_2_AFN

Pres_2_4_AFN-e

Python

Notebook_Implementación AFD.ipynb

Python

Notebook_Implementación AFN.ipynb

Python

Notebook_Implementación AFN-e.ipynb

  • 3. LENGUAJES REGULARES
  • Expresiones Regulares
  • Álgebra de las expresiones
  • Propiedades de las Expresiones Regulares




Pres_3_1_ExpresionesRegulares

Pres_3_2_PropiedadesER

  • 4. LENGUAJES INDEPENDIENTES DEL CONTEXTO
  • Gramáticas independientes del contexto
  • Árboles de Derivación
  • Autómatas de Pila




Pres_4_1_Gramáticas

Pres_4_2_ArbolesDerivación

Pres_4_3_AutómatasDePila

Python

Notebook_GLC.ipynb

Python

Notebook_PDA.ipynb

  • 5. MAQUINAS DE TURING (MT)
  • Introducción MT
  • MT múltiples cintas y MT múltiples pistas
  • Autómatas con MT




Pres_5_1_MT1

Pres_5_2_MT2

Pres_5_3_MT3

Python

Notebook_MT1.ipynb

Python

Notebook_MT2.ipynb

Python

Notebook_MT-multitape

Python

(Python file for MT-multitape)

  • 6. PROBLEMAS INTRATABLES
  • Indecibilidad y MT Universal
  • Problemas P y NP




Pres_6_1_PNP

Cronograma 2018-2

Proyectos Previos

Referencias

1. SUDKAMP, T. Languages and Machines, Addison-Wesley Publishing Company, Inc, Reading, Mass, 1988.

2. PENROSE., R., The Emperor's New Mind : Concerning, Computers, Minds An The Laws Of Physics.

3. HOPCROFT, J.E., and J. D. ULLMAN. Introducción to Automata Theory, Languages and Computation Addison-Wesley Publishing Company, Inc, Reading, Mass, 1979.

4. KELLEY, Dean. Teoría de autómatas y lenguajes formales, Prentice Hall.

Online Courses

1. MIT. Automata, Computability, and Complexity [+]

2. Standford. Automata


Cursos Previos

Pres 2018-1

Noteb 2018-1

Pres 2016-2

Noteb 2016-2

Pres 2017-1

Noteb 2017-1

OTROS RECURSOS