Lenguajes formales

Un lenguaje formal es una especie de generalización del concepto de lenguaje al que estamos acostumbrados en la vida cotidiana.

Conceptos básicos

Para empezar, podemos imaginar un lenguaje formal como un lenguaje corriente, por ejemplo el español. ¿De qué se compone un lenguaje así? Se compone de palabras, que luego unimos en oraciones. Las oraciones no nos interesarán; nos interesarán solo las palabras. ¿De qué se componen las palabras? De letras del alfabeto. Por eso empezaremos por el alfabeto.

Un alfabeto es un conjunto cualquiera no vacío. A los elementos del alfabeto los llamamos símbolos. Si hablamos del español, será el alfabeto español habitual, con letras minúsculas y mayúsculas, además de las variantes con tilde y diéresis. Si no quisiéramos describir el español, sino, por ejemplo, números, el alfabeto contendría las diez cifras. El alfabeto se suele denotar con el símbolo Σ.

Por palabra, o también cadena, entendemos una sucesión finita de símbolos de un alfabeto Σ. Si tenemos, por ejemplo, el alfabeto Σ= {a,b,c,d,e,…, z}, entonces una palabra es, por ejemplo, la sucesión «hola» o «perro», pero no «mañana» (no tenemos la letra «ñ»), «Hugo» (no tenemos la «H» mayúscula) ni «buenas tardes» (no tenemos el espacio). La longitud de una palabra es el número de símbolos de los que se compone.

Concatenación de palabras: si tenemos dos palabras a = a₁a₂… a_n y b = b₁b₂… b_m, la concatenación de ambas da la palabra ab = a₁a₂… a_nb₁b₂… b_m. Ejemplo: al concatenar las palabras «hola» y «perro» resulta la palabra «holaperro». La concatenación se denota con un círculo, es decir, a ∘ b, o bien no se denota de ninguna manera y simplemente se escriben las palabras una detrás de otra, sin ningún símbolo especial.

La palabra vacía se denota ε y es la palabra que tiene longitud cero. Si concatenamos una palabra a = a₁… a_n con la palabra vacía ε, obtenemos de nuevo la palabra a. Es decir, se cumple a ∘ ε = a.

La clausura de Kleene del alfabeto Σ es el conjunto de todas las palabras que podemos formar con el alfabeto Σ, incluida la palabra vacía. La clausura se denota Σ^∗. Si tenemos el alfabeto binario Σ= {0, 1}, se cumple

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

A veces usamos también la clausura positiva del alfabeto, que son de nuevo todas las palabras que podemos formar con el alfabeto, salvo la palabra vacía. La clausura positiva se denota Σ⁺ y se cumple Σ⁺ = Σ^∗ ∖ {ε}.

Ejemplos de alfabetos

• Volvamos al ejemplo del español. Cada palabra española se encuentra en la clausura de un alfabeto que contenga las letras minúsculas y mayúsculas y las letras con tilde o diéresis (y quizá también el guion «-»). Si a este alfabeto le añadimos el espacio y los signos de puntuación (coma, punto, exclamación, interrogación, …), la clausura contiene todas las oraciones que podemos formar en español. Por supuesto, en esta clausura habrá también oraciones como «sadflsf kasdf kagrjewiáéñker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf», que, aun así, tienen más sentido que muchos comentarios en internet.

• Si nuestro alfabeto contiene todas las cifras Σ= {0, 1, …, 9}, en la clausura estarán todos los números naturales —y algunos más—. Habrá, en efecto, números que empiezan por cero, como 00054, o el cero solo, y además estará la palabra vacía, que, por supuesto, no es ningún número.

• El alfabeto debe ser no vacío, así que el alfabeto más pequeño tiene al menos un símbolo. Por ejemplo, para el alfabeto Σ= {!} obtendríamos la clausura Σ^∗ = {ε, !, !!, !!!, !!!!, …}, es decir, un conjunto de palabras en el que, para cada n ∈ ℕ ∪ {0}, existe una palabra con n signos de exclamación y ninguna otra palabra más.

• Sea Σ= {qw,c}. Este es un alfabeto muy raro, porque contiene la palabra qw. Esta notación no suele usarse, porque resulta confusa y extraña, pero podemos imaginarlo como si pegáramos las letras «q» y «w» de modo que formen un único carácter. Entonces podemos ver la palabra «qw» como el símbolo «qw». Si con este símbolo formáramos la palabra «qwcqw», esta tendría longitud tres: estaría compuesta por los símbolos «qw», «c» y «qw». No nos encontraremos con alfabetos así muy a menudo, pero hay situaciones en las que necesitamos usar símbolos que se componen de varios símbolos.

Lenguaje formal

Un lenguaje (formal) sobre el alfabeto Σ es un subconjunto cualquiera de Σ^∗. Para un lenguaje L sobre el alfabeto Σ se cumple, por tanto, L ⊆ Σ^∗. Ejemplos de lenguajes:

• En la parte anterior hemos definido el alfabeto de las cifras Σ= {0, 1, …, 9}. La clausura son todas las palabras formadas solo por cifras. Si añadimos la regla de que la palabra no puede empezar por cero y no puede ser vacía, obtenemos el conjunto de los números naturales ℕ. Se cumple la relación ℕ ⊆ Σ^∗, así que ℕ es un lenguaje sobre el alfabeto Σ.

• Al conjunto de cifras anterior podemos añadir el signo menos «-», de modo que Σ= {0, 1, …, 9, −}. La clausura son todas las palabras que se componen de cifras o del signo menos. Eso significa, sin embargo, que en la clausura hay también palabras como «12-84-», «1-5-8» o «-». El lenguaje de los números enteros ℤ lo construimos añadiendo tres reglas:

  • El signo menos no aparece en la palabra o aparece al principio de la palabra.
  • La primera cifra de la palabra no puede ser cero, salvo en la palabra «0».
  • Toda palabra debe contener al menos una cifra.

  Este conjunto describe el conjunto de los números enteros y es un subconjunto de Σ^∗; por tanto, es un lenguaje sobre el alfabeto Σ.

• Sea Σ= {0, 1}. La clausura son entonces todas las palabras que se componen de ceros y unos. Podemos definir un lenguaje L sobre este alfabeto, por ejemplo, como el conjunto de todas las palabras que tienen exactamente tres unos. Podemos ser incluso más creativos y decir que el lenguaje L será el conjunto de todas las palabras que representan un formato válido de archivo docx (lo que sale de Word).

• Sigamos con el alfabeto binario Σ= {0, 1}. Toda cadena de caracteres (los caracteres normales que tienes en el teclado) se puede convertir a forma binaria, es decir, a ceros y unos, y de nuevo a la inversa, por ejemplo mediante la tabla ASCII (o, más exactamente, la tabla ASCII convierte caracteres en números, y los números del sistema decimal se pueden convertir a números en el sistema binario). Así podemos definir el lenguaje de todas las palabras que corresponden a un correo electrónico válido, y seguirá siendo un lenguaje sobre el alfabeto binario.

Concatenación de lenguajes: también se pueden concatenar lenguajes. La definición será parecida a la del producto cartesiano de conjuntos. Sean dos lenguajes L₁ y L₂. Con su concatenación L₁ ∘ L₂ obtenemos un nuevo lenguaje, que definimos así:

$$L_1\circ L_2=\{w_1\circ w_2\mid w_1\in L_1,w_2\in L_2\}$$

Es decir, tomamos todas las palabras del lenguaje L₁ y las concatenamos con todas las palabras del lenguaje L₂. Ejemplo: sean

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,hola\}\end{array}$$

Entonces se cumple:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0hola,1a,1b,1hola\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,hola0,hola1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Hasta ahora, para describir lenguajes hemos usado el lenguaje corriente: simplemente hemos descrito con palabras cómo debe ser el lenguaje. Eso resulta muy poco práctico, así que se introducen maneras más formales de definir un lenguaje. La primera de ellas es la gramática.