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