De Wikiversidad

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