Lenguajes naturales y formales, palabra, propiedades de las palabras, cardinalidad de un lenguaje formal, sublenguajes, lenguajes formales infinitos, lenguaje universal sobre un alfabeto.
La potencia (abc)2 es una palabra del lenguaje.
La cadena ab es un prefijo de todas las palabras no vacías; lo mismo ocurre con el sufijo bc.
Finalmente, b es una subpalabra de todas las palabras no vacías de este lenguaje.
La concatenación de dos palabras produce una cadena que no siempre es una palabra del lenguaje, como se observa en el ejemplo anterior y en el ejemplo que sigue.
Sea el lenguaje L = {a2n+1 / 0 ≤ n ≤ 200}. Este lenguaje está formado por 201 palabras, cada una de las cuales tiene un número impar de letras a. Por lo tanto, si n = 0, la palabra es a; si n = 1, la palabra es aaa; etc. Si se concatenan dos palabras cualesquiera de L, el resultado será una cadena con una cantidad par de letras a, ya que la suma de dos números impares produce un número par.
En consecuencia, la concatenación de dos palabras cualesquiera de este lenguaje produce una cadena que nunca es una palabra de L.
La cardinalidad de un LF es la cantidad de palabras que lo componen.
L = {a, ab, aab} es un lenguaje de cardinalidad 3 sobre el alfabeto {a, b}.
Dado que un Lenguaje Formal es un conjunto, un SUBLENGUAJE es un subconjunto de un lenguaje dado.
Ejemplo 38
Sea L1 = {a, ab, aab}. Entonces, L2 = {ab, aab} es un sublenguaje de L1, mientras que L3 = { } es el sublenguaje vacío de L1.
Todos los lenguajes ejemplificados hasta el momento han sido LENGUAJES FORMALES FINITOS, es decir: lenguajes con un número finito de palabras.
Sin embargo, los LFs también pueden ser INFINITOS, lo que significa que estos lenguajes pueden tener una cantidad infinita de palabras, pero cada una de longitud finita (no existen las palabras de longitud infinita).
Nota 6: Las propiedades de las palabras que han sido ejemplificadas anteriormente se aplican también a los lenguajes infinitos.
Ejemplo 39 L = {an / n ≥ 1} es un LF infinito ya que no existe un límite superior para el supraíndice n.
Cada palabra de este lenguaje está formada por una secuencia de una o más aes. Por ello, la concatenación de dos palabras cualesquiera de este lenguaje producirá siempre otra palabra del lenguaje L.
Por esta propiedad, se dice que este lenguaje L es cerrado bajo la concatenación.
Este lenguaje no es cerrado bajo la concatenación ya que, por caso: si consideramos sus dos palabras de menor longitud –a y ab– y las concatenamos, obtenemos la cadena aab, que no es una palabra de este lenguaje.
Dado un alfabeto ∑, el LENGUAJE UNIVERSAL sobre este alfabeto es un lenguaje infinito que contiene todas las palabras que se pueden formar con los caracteres del alfabeto ∑, más la palabra vacía.
Se lo representa con la notación ∑*, que se lee “sigma clausura” o “sigma estrella”.
Importante: acabamos de introducir un nuevo operador que representamos con el supraíndice *. Este es un operador unario (sobre un solo operando), como lo es la potenciación en matemáticas.
Se lo denomina “clausura de Kleene” o “estrella de Kleene”, y será muy utilizado en próximos capítulos.
Una propiedad fundamental del Lenguaje Universal es que es cerrado bajo concatenación (por eso la denominación de “sigma clausura”).
Ejemplo 41 Si ∑ = {a, b}, entonces el Lenguaje Universal para este alfabeto es:
∑* = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …, aabaabbbab, …},
y la concatenación de palabras de este lenguaje siempre produce una palabra del Lenguaje Universal.
¿Puede encontrar un caso en que esta afirmación sea falsa?
Cualquier lenguaje L sobre el alfabeto ∑ es un sublenguaje de ∑*. Por lo tanto, existen infinitos lenguajes sobre un alfabeto dado.
