Material de Libre Acceso.

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.

Árbol de derivación:

Estructura en forma de árbol que permite determinar si una palabra pertenece a un lenguaje. Los árboles de derivacióntienen como raíz al símbolo inicial y se colocan como hijos de la raíz, a los signos del lado derecho de la composición, para después sustituir cada símbolo no terminal por medio de la composición correspondiente hasta obtener un árbol cuyas hojas sean solamente símbolos terminales.

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.

Cerradura de Kleene o cerradura estrella (∑*):

Es el lenguaje con todas las cadenas que se pueden formar con el alfabeto (∑).

Composiciones:

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

D

Diagrama de transición:

En este tipo de diagrama los estados se representan por medio de un círculo con el nombre del estado dentro de ella. Los estados de aceptación o finales se distinguen porque tienen doble círculo, las transiciones se representan por aristas y se etiquetan con un símbolo del alfabeto. El estado inicial se distingue porque se hace incidir sobre él una flecha.

Diagramas sintácticos:

Forma ilustrativa para representar una gramática por medio de gráficas dinámicas que permiten determinar en forma más clara si una palabra pertenece a un lenguaje. En un diagrama sintáctico los símbolos no terminales se representan dentro de un cuadro, y los símbolos terminales se encierran dentro de un círculo.

E

Expresiones Regulares:

Forma de expresar los lenguajes regulares con la finalidad de facilitar la manipulación y simplificación de los mismos.

G

Gramática:

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

Gramática regular:

Es aquella en donde el lado izquierdo de la composición es un símbolo no terminal y el lado derecho tiene uno o más símbolos, incluyendo a lo más un símbolo no terminal.

Gramáticas libres de contexto:

Son aquellas en donde el lado izquierdo de cada composición es un símbolo no terminal y el lado derecho consta de uno o más símbolos terminales y/o no terminales. Este tipo de gramáticas es la que se usa en el desarrollo de lenguajes formales.

Gramáticas sensibles al contexto:

Son aquellas en donde no se pone ninguna restricción a las composiciones de la gramática. Son gramáticas muy complejas de estudiar debido principalmente a la libertad que se tiene para formar palabras de 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.

R

Representación BNF (Backus-Naur):

Técnica para representar gramáticas en donde una composición puede estar integrada por varias reglas de derivación. En la gramática BNF la flecha () de una composición se indica con “::=” y un mismo símbolo no terminal implica diferentes cadenas de símbolos, en esta gramática es posible compactar la información usando para ello el carácter “/”.

S

Símbolo inicial:

Símbolo que permite iniciar la derivación de palabras propias de un lenguaje.

Símbolo no terminal:

Símbolo que puede sustituirse por medio de una composición para la formación de palabras más complejas.

Símbolo terminal:

Símbolo que ya no es posible descomponer en la formación de palabras propias de un lenguaje.

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.

Teoría de la computabilidad:

Es la parte de la computación que analiza y determina los problemas que pueden resolverse por medio de un algoritmo o bien por alguna de las máquinas de Turing.