Curso de Teoría de la Computabilidad

Unidad I

1. Conocimientos matemáticos:

 1.1. Conjuntos
   1.1.1. Teoria de Conjuntos
   1.1.2. Operaciones con Conjuntos
 1.2. Definición de alfabeto
 1.3. Propiedad de las Cadenas "Strings"

Unidad II

2. Autómatas finitos y lenguajes regulares

 2.1. Autómatas finitos determinísticos (DFA’S).
 2.2. Autómatas finitos no determinísticos (NFA’S).
 2.3. Autómatas finitos no determinísticos con movimiento ε (NFA- ε).
 2.4. Expresiones regulares.
 2.5. Lenguajes Regulares.
 2.6. Funciones Recursivas.
 2.7. PUMPING LEMMA O LEMA de bombeo para lenguajes regulares.

Unidad III

3. Autómatas de pila y lenguajes libres de contexto.

 3.1. Autómatas de pila o PUSH-DOWN (PDA).
 3.2. Gramáticas libres de contexto (CFG’S).
 3.3. PUMPING LEMMA para lenguajes  libres de contexto.
 3.4. Notación BNF.
 3.5. Árboles Sintacticos.

Unidad IV

4 - Autómatas lineales y lenguajes sensibles al contexto.

 4.1. Autómatas lineales (LBA).
 4.2. Lenguaje natural o sensible al contexto.

Unidad V

5. Máquinas de turing y lenguajes recursivos enumerables.

 5.1. Definición de una máquina de turing .
 5.2. Funciones de una máquina de turing.
 5.3. Lenguajes aceptados por las máquinas de turing.
 5.4. Extesiones de las máquinas de turing.
 5.5. HALTING PROBLEM.
 5.6. Hipótesis de CHURCH.

ABREVIATURAS TÉCNICAS

ABREVIATURA	SIGNIFICADO EN INGLES	SIGNIFICADO EN ESPAÑOL
BNF	Backus-Naur Form	Forma de Backus-Naur
CFG	Context-Free Grammar	Gramática Libre de Contexto
CFL	Context-Free Language	Lenguaje Libre de Contexto
CSG	Context-Sensitive Grammar	Gramática Sensible al Contexto
CSL	Context-Sensitive Language	Lenguaje Sensible al Contexto
DFA	Deterministic Finite Automaton	Autómata Finito Determinístico
IA	Artificial Intelligence	Inteligencia Artificial
LBA	Linear-Bounded Automata	Autómata Lineal Acotado
LEX	Lexical Analizer	Generador de Analizadores Léxicos
LISP	List Processor	Procesador de Listas
NFA	Nondeterministic Finite Automaton	Autómata Finito No determinístico
PDA	Push-down Automata	Autómata de Pila
PROLOG	Programming Logic	Programación Lógica
r. e.	Recursively Enumerable	Recursivamente Enumerable
TM	Turing Machine	Máquina de Turing
YACC	Yet Another Compiler-Compiler	Otro Compilador de Compiladores Más