Portafolio Teoria

PORTAFOLIO DE
EVIDENCIAS
Teoría de la Computación

Alumna: Jaqueline Caamal Cámara

Maestro: Alejandro Pasos Ruíz

Ingeniería en Computación

Índice
UNIDAD 1 .......................................................................................................... 2
Definiciones .................................................................................................... 2
Definición deExpresión Regular ..................................................................... 3
UNIDAD 2 .......................................................................................................... 4
Autómata Finito Determinista .......................................................................... 4
Proceso de verificación si 2 AFD sonequivalentes......................................... 5
Definición Autómata Finito No Determinista .................................................... 7
Conversión AFN-AFD ..................................................................................... 8
Describir una aplicación de un AFD .............................................................. 11
UNIDAD 3........................................................................................................ 12
Definición formal de gramática y gramática regular ...................................... 12
Definición Gramática Libre de Contexto........................................................ 12
Definición Árbol de derivación ....................................................................... 13
Aplicación GLC ................................................ ¡Error!Marcador no definido.
UNIDAD 4 ........................................................................................................ 14
Definición Autómata de Pila .......................................................................... 14
Proceso de conversión AP – GLC................................................................. 14
Compilador LL – LR...................................................................................... 16
Tabla de Previsión ........................................................................................ 17
UNIDAD 5 ........................................................................................................ 18
Definición de máquina de Turing.................................................................. 18
Descripción delproblema del paro ................................................................ 19
Relevancia en la computación ...................................................................... 19
UNIDAD 6 ........................................................................................................ 21
Eficiencia en algoritmos computacionales .................................................... 21Operaciones Elementales ............................................................................. 21
Como se calculan las operaciones elementales en algoritmos iterativos ...... 22
Definir la notación O, Teta, Omega y para que se usa en algoritmos ........... 22
Definir problemas P,NP, NP-Completos ....................................................... 24
Ejemplos de problemas NP-completos......................................................... 25
Referencia ....................................................................................................... 27

1

UNIDAD 1
Definiciones
Alfabeto: Un alfabeto es un conjunto no vacío de símbolos. Así, el alfabeto del
idioma español, Σ= {a, b, c,. . ., z}, es sólo uno de tantos alfabetos posibles.
Símbolo: Es simplemente unarepresentación distinguible de cualquier
información. Los símbolos pueden ser cualesquiera, como w, 9, #, etc.
Cadena (Palabras): Con los símbolos de un alfabeto es posible formar
secuencias o cadenas de caracteres, tales como mxzxptlk, balks, r, etc. Las
cadenas de caracteres son llamadas también palabras.
Un caso particular de cadena es la palabra vacía, Ɛ, la cual no tiene ninguna
letra.
Lenguaje: Un...