Glosario de términos Lenguajes y Autómatas

Conjunto:

Un conjunto es una colección de objetos llamados elementos del conjunto. (Kelley, 1995).

La idea de un conjunto como una colección de individuos u objetos no es, para un verdadero matemático, suficientemente precisa, y se parece a la noción de clase; sin embargo, para nuestros propósitos es suficiente. (Brena, 2003).

Conjunto Universal:

Es conveniente pensar que todos los elementos se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjunto universal. Si A es un conjunto, entonces U – A es el conjunto de todos los elementos que no están en A. Conviene denotar tales complementos mediante A'; de forma que U – A = A'. Obsérvese que 0' = U y U' = 0. (Kelley, 1995).

El conjunto universo es aquel que contiene todos los elementos posibles, denotado por U. (Brena, 2003).

Unión:

La unión de conjuntos A y B se denota por A ᑌ B y es un conjunto formado por los elementos que aparecen en A, en B o en ambos. Por tanto:

A ᑌ B = { x | x € A o x € B }

(Kelley, 1995).

Denotada por A ᑌ B, que contiene los elementos del conjunto A y también los del conjunto B, es decir, A ᑌ B = { x | x € A o x € B }. (Brena, 2003).

Intersección:

La intersección de A y B es el conjunto A ∩ B = { x | x € A y x € B }.

Obsérvese que si x € A ∩ B entonces se puede decir que x aparece simultáneamente en A y B. (Kelley, 1995).

Escrita A ∩ B, que contiene los elementos que pertenecen simultáneamente al conjunto A y al conjunto B, es decir A ∩ B = { x | x € A y x € B }. (Brena, 2003).

Diferencia:

A – B está compuesto por todos los elementos de A que no están también en B:

A – B = { x | x € A y x /€ B }

(Kelley, 1995).

A – B, que contiene los elementos de A que no están en B, esto es:

A – B = { x | x € A y x /€ B}.

(Brena, 2003).

Complemento:

Los complementos pueden estar formados con respecto a U o a un conjunto B (complemento relativo):

Complemento de A con respecto a U: A' = U – A.

Complemento de A con respecto a B: B – A = { x | x € B y x /€ A }

(Kelley, 1995).

Es un caso particular de la diferencia, cuando el primer conjunto es considerado como el universo que contiene todos los elementos posibles, sea U un universo, entonces el complemento del conjunto A, denotada por Ac contiene los elementos del universo que no están en A. Claramente A ᑌ Ac = U, para todo conjunto A; además A ∩ Ac = {}. (Brena, 2003).

Alfabeto:

Un conjunto no vacío y finito de símbolos se le conoce como alfabeto. (Kelley, 1995).

Un alfabeto es un conjunto no vacío de símbolos. (Brena, 2003).

Cadena:

Cada símbolo de un alfabeto es una cadena sobre dicho alfabeto. (Kelley, 1995).

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. (Brena, 2003).

Cadena vacía:

La cadena vacía, la cual se denota por el símbolo £ es una palabra sobre cualquier alfabeto. (Kelley, 1995).

Un caso particular de cadena es la palabra bacía denotada por £, la cual no tiene ninguna letra. (Brena, 2003).

Prefijo:

Si w y x son palabras, se dice que x es prefijo de w, si para alguna cadena se obtiene que w =xy. (Kelley, 1995).

Para una palabra w, un prefijo de w es cualquier subcadena s con que inicia w, es decir, sz = w, tal que w, z, s € Ʃ*. (Brena, 2003).

Sufijo:

Si w y x son palabras, se dice que x es prefijo de w, si para alguna cadena se obtiene que w =yx. (Kelley, 1995).

Para una palabra w, un sufijo de w es cualquier subcadena s con que termina w, es decir, zs = w, tal que w, z, s € Ʃ*. (Brena, 2003).

Subcadena:

Una cadena de w es una subcadena de otra cadena z si existen las cadenas x e y para las cuales z =xwy. (Kelley, 1995).

Una palabra v es subcadena de otra w cuando existen cadenas x, y – posiblemente vacías – tales como xvy = w. (Brena, 2003).

Subsecuencia:

La subsecuencia surge por la eliminación de cero o más símbolos de una cadena o palabra donde se tiene que respetar el orden de los símbolos. (Kelley, 1995).

Una subsecuencia es la eliminación de 0 o más elementos de una cadena, siendo una sucesión ordenada de elementos, donde el orden sí importa. (Brena, 2003).

Inversa:

La inversa o transpuesta de una palabra w es la imagen reflejada de w. Para denotar la inversa de w se usa wI. (Kelley, 1995).

Se llama inverso de una relación R, denotado por R-1, a aquella en donde se invierte el orden de los pares ordenados, esto es:

R-1 = { (y, x) | (x, y) € R }

(Brena, 2003).

Longitud:

Si w es una cadena sobre cualquier alfabeto, su longitud se denota mediante el símbolo |w|. La longitud de w es el número de símbolos que tiene la cadena. (Kelley, 1995).

El tamaño de un conjunto es el número de elementos que contiene, y se representa como |A| para un conjunto A. (Brena, 2003).

Lenguaje:

Un lenguaje es un conjunto de palabras. (Kelley, 1995).

Un lenguaje es simplemente un conjunto de palabras. (Brena, 2003).

Concatenación:

Si w y z son cadenas, la concatenación de w con z es la cadena que se obtiene al añadir la cadena w a la cadena z. Por ejemplo, si w = 'banana' y z = 'rama', la concatenación de w con z es la cadena 'bananarama'. La concatenación de las palabras w y z se denota como wz. (Kelley, 1995).

Cuando escribimos varias palabras o caracteres uno a continuación de otro, se supone que forman una sola palabra (se concatenan). La notación usada para denotar la concatenación de dos cadenas a y b es ab. (Brena, 2003).

Cerradura de Kleene:

Si A es un lenguaje sobre algún alfabeto Σ, se define la cerradura de Kleene o cerradura de estrella de un lenguaje A como:

(Kelley, 1995).

Si L es un lenguaje, L*, llamado cerradura de Kleene de L, es el más pequeño conjunto que contiene:

La palabra vacía

El conjunto L

Todas las palabras formadas por la concatenación de miembros de L*

(Brena, 2003).

Cerradura positiva:

Definimos Cerradura positiva de A como A+ como:

(Kelley, 1995).

Si L es un lenguaje, L+, llamado cerradura positiva de L, es el conjunto que contiene:

El conjunto L

Todas las palabras formadas por la concatenación de miembros de L+.

(Brena, 2003).

Compilador:

Un compilador es un programa

...