Glosario

• A

Alfabeto:

Conjunto de símbolos con el cual se forman palabras de un lenguaje.

Autómata finito (AF):

Gramática regular que permite la derivación de palabras de un lenguaje. Los AF constan de cinco elementos fundamentales AF=(∑, E, F, s, δ). Un alfabeto (∑), un conjunto de estados (E), estado inicial (s), un conjunto de estados finales (F) y una función δ: E×∑E que permite determinar cuál es el estado siguiente.

Autómata Finito Determinístico (AFD):

Es aquel en donde es posible determinar claramente cuál es el estado siguiente.

Autómata finito no determinístico (AFN):

Es aquel en donde la función de estado siguiente, no conduce a un estado único determinado.

• C

Cadena:

Es una secuencia de símbolos que se coloca uno seguido del otro.

Cadena vacía (ε):

Es aquella cadena que no tiene símbolos.

Composiciones:

Conjunto de reglas que se deben usar para la estructuración de las palabras válidas en el lenguaje.

• G

Gramática:

Están integradas por el alfabeto y las composiciones para la estructuración correcta de las palabras validas en un lenguaje.

• L

Lenguaje:

Es un conjunto de símbolos (o palabras) y métodos para estructurar y combinar dichos símbolos.

Lenguaje natural:

Conjunto de símbolos y reglas para formar palabras, frases y oraciones que se utilizan para la comunicación entre las personas. Este tipo de lenguajes también se conocen como idiomas, así es el caso del idioma español, francés, italiano, inglés etc.

Lenguajes formales:

Lenguajes de menor capacidad para simular y modelar lenguajes naturales, como el lenguaje binario, Java, C, Basic o Pascal que se utilizan en la comunicación con las computadoras.

• M

Máquina de estado finito:

Es una forma especial de representar los autómatas finitos, en donde no existen estados aceptados y donde los símbolos de salida se colocan juntamente con los símbolos de entrada en cada una de las aristas de la máquina.

Máquina de Turing (MT):

Consiste de una cinta que se extiende de manera infinita en donde se escribe o se lee información por medio de una cabeza de lectura-escritura.

• P

Programa fuente: es aquel que nos permite escribir un algoritmomediante un lenguaje formal. Por eso al código desarrollado al programar se le llama código fuente. 

Programa objeto: es el resultado de traducir un programa fuente para obtener un lenguaje comprensible por la máquina.  

• T

Tabla de transición:

Tabla que concentra la información de un autómata así como los valores que puede tomar la función de estado siguiente.

Teoría de la complejidad:

Es la parte de la computación que se encarga de analizar la cantidad de recursos necesarios para resolver un problema como son tiempo y espacio.