Page 35 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

35

CADENAS

En matemáticas, lógica, y ciencias de la computación, un lenguaje formal es un lenguaje cuyos
símbolos primitivos y reglas para unir esos símbolos están formalmente especificados y definidos;

y en consecuencia se ajustan al rigor de la regla. Al conjunto de los símbolos primitivos se le
llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se le llama la gramática
formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se la llama una
fórmula bien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es
idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el
alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una
longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de
fórmulas bien formadas.

Alfabeto:

Un alfabeto es un conjunto de símbolos finito y no vacío. Convencionalmente, se utiliza el
símbolo σ, para referirse a él.
Ejemplos de alfabetos conocidos en el ámbito computacional:
1. Σ= {0, 1}, el alfabeto binario
2. Σ= {a, b,…, z}, el conjunto de todas las letras mayúsculas
3. El conjunto de todos los caracteres ASCII o el conjunto de todos los caracteres ASCII
imprimibles.

Potencias de un alfabeto:

Si σ es un alfabeto, podemos expresar el conjunto de todas las cadenas de una determinada

longitud, de dicho alfabeto, utilizando una notación exponencial. Definimos para que sea el
conjunto de las cadenas de longitud k, tales que cada uno de los símbolos de las mismas pertenece
a σ.

0
Nótese que = {∈} sea cual sea el alfabeto. O sea ∈ es la única cadena existente cuya longitud
es 0. O sea ∈ es la cadena vacia, también se designa con λ o ω en algunos libros.

1
2
Si σ ={ 0, 1} (esto es un alfabeto), entonces = {0,1}, = {00, 01, 10, 11}
= {000, 001, 010, 011, 100, 101, 110,111}. Las anteriores son conjuntos de cadenas.
3
Concluyendo: el conjunto de todas las cadenas de un alfabeto σ se representa por o sea que
∗
si: {0,1} = {є, 0,1,00,01,10,11,000, … } que es lo mismo que expresar:
∗
1
2
0
∗
= ⋃ ⋃ ⋃ …..
Cadenas o cadenas de caracteres:
Una cadena de caracteres (que en ocasiones se denomina palabra) es una secuencia finita de
símbolos seleccionados de algún alfabeto. Por ejemplo, 01101 es una cadena del alfabeto binario
σ= {0, 1}. La cadena 111 es otra cadena de dicho alfabeto. En general, una cadena es una
secuencia de símbolos finita. En consecuencia cuando se habla de símbolos se hace referencia a
los símbolos de un alfabeto particular. Así las cosas si el alfabeto es {a,b}, cadenas o palabras de
ese alfabeto particular pueden ser: {aabb}, {abab}, {aaab} , etc. En fin cualquier combinación de