Nociones y notaciones básicas1
En este capítulo introduciremos las nociones y notaciones básicas sobre teoría de lenguajes que utilizaremos a lo largo del curso.
Un alfabeto es un conjunto finito a cuyos elementos llamaremos símbolos. Usualmente lo denotaremos con el símbolo \Sigma (Sigma). Aunque un alfabeto es un conjunto finito cualquiera, frecuentemente sus elementos serán denotados con letras o dígitos. Por ejemplo, el conjunto \Sigma=\{a,b\} sería un posible alfabeto.
Una palabra construida sobre un cierto alfabeto es una lista de símbolos de ese alfabeto.
Ejemplo 1 Sobre el alfabeto \Sigma=\{a,b\}, podemos tener la palabra ab, la palabra formada por el símbolo a y el símbolo b, o la palabra bbb (entre muchas otras). También a sería una palabra: en este caso con un solo símbolo, una palabra de longitud uno.
Sobre cualquier alfabeto podremos construir siempre la palabra de longitud 0 o palabra vacía. Esta la notaremos con el símbolo \lambda (lambda).
Usaremos las letras u, v y w con posibles subíndices para denotar palabras. Del siguiente modo denotaremos la longitud de una palabra u con |u|.
Ejemplo 2 |ab|=2, |bbb|=3, |a|=1 y |\lambda|=0.
Esta notación se extiende para denotar ocurrencias de una palabra dentro de otra. El numero de occurrencias de la palabra w dentro de la palabra u se denota con |u|_w.
Ejemplo 3
- |a|_a=1, el número de ocurrencias de a en a es 1,
- |bbb|_b=3, el número de ocurrencias de b en bbb es 3 y
- |bbb|_{bb}=2, el número de ocurrencias de la palabra bb en bbb es 2, la ocurrencia que aparece a posición uno y la que aparece a posición dos.
Con u[i] denotamos el símbolo i-esimo de la palabra u.
Ejemplo 4
- ab[1]=a, la palabra ab a posición uno tiene una a, y
- ab[2]=b, la palabra ab a posición dos una b.
Mediante la operación producto representada con un punto \cdot como operación enfija (o a veces sin escribir nada) representamos la concatenación de dos palabras. La concatenación de las palabras u y v es u\cdot v o uv. La concatenación es una operación que da como resultado la concatenación de las respectivas listas.
Ejemplo 5 La concatenación de la palabra ab con la palabra bbb, es decir (ab)\cdot (bbb), produce la palabra abbbb.
La palabra vacía \lambda es el elemento neutro de la concatenación, es decir que por cualquier palabra u, u\cdot \lambda=\lambda\cdot u=u, cosa que se puede comprobar fácilmente. Además no es difícil comprobar que la concatenación de palabras es una operación asociativa, es decir que u\cdot(v\cdot w)=(u\cdot v)\cdot w para todas palabras u, v, w.
Mediante \Sigma^* (Sigma estrella) representaremos el conjunto de todas las palabras posibles que se pueden construir sobre el alfabeto \Sigma.
Ejemplo 6 Si \Sigma=\{a,b\} podremos construir todas las palabras posibles sobre \Sigma empezando por la palabra de longitud cero \lambda, las dos palabras de longitud 1, a y b, las cuatro palabras de longitud dos, aa, ab, ba, bb y así sucesivamente. Es decir, \Sigma^*=\{\lambda, a, b, aa, ab, ba, bb, \dots\}\ .
Un lenguaje sobre un alfabeto \Sigma es un subconjunto cualquiera de \Sigma^*. Los lenguajes los denotaremos solitamente con la letra L.
Ejemplo 7 El lenguaje L de las palabras sobre \{a,b\} y del longitud múltiple de 2 lo podríamos representar de esta manera: L=\{w\in \{a,b\}^* \mid |w|\in \dot 2\}\ . Fijémonos en que estamos usando esencialmente la notación clásica de conjuntos donde ponemos en primer lugar la variable por la que implícitamente se puede sustituir a una palabra y a la derecha del simbulo \mid describimos la propiedad que debe cumplir esa palabra para pertenecer efectivamente al conjunto. El mismo conjunto de palabras de longitud múltiple de dos lo podemos representar de forma más explícita como sigue L=\{\lambda, aa, ab, ba, bb, aaaa, aaab, \dots\}\ .
Ejemplo 8 El lenguaje L de las palabras sobre \{a,b\} que tienen alguna ocurrencia de alguna a. Nuevamente usamos la notación clásica de conjuntos: L=\{w\in \{a,b\}^* \mid \exists w_1,w_2\ w=w_1aw_2\}\ . En este caso la propiedad viene expresada mediante un cuantificador existencial. Si w coincide con la concatenación de una palabra cualquiera w_1 seguida de a seguida de otra palabra cualquiera w_2 es que cumple nuestra propiedad.
Alternativamente, podríamos representar L sacando provecho de la notación para representar el número de ocurrencias de a dentro de una palabra: L=\{w\in \{a,b\}^*\mid |w|_a\geq 1\}\ .
Ejemplo 9 El lenguaje L de las palabras sobre \{a,b\} tales que toda ocurrencia de a viene seguida inmediatamente de una ocurrencia de b. Una posible manera de denotarlo es esta: L=\{w\in \{a,b\}^* \mid \forall w_1,w_2 (w=w_1aw_2 \implies \exists w_2'\ w_2=bw_2')\}\ . Entendamos cómo funciona el cuantificador universal (\forall) combinado con la implicación (\implies). Fijaos que para aquellos w_1 y w_2 tales que w no coincide con w_1 seguido de a, seguido de w_2 resulta que el antecedente de la implicación es falso y por tanto la implicación es cierta. Ello nos garantiza que el consecuente debe cumplirse simplemente para aquellas particiones de la palabra w que nos interesan.
Una forma alternativa de describir este lenguaje L sería la siguiente: L=\{w\in \{a,b\}^* \mid w=\lambda \lor (|w|_{aa}=0 \land \exists w'\ w=w'b)\}\ .
Nuevamente sacamos provecho de la notación adicional que hemos introducido para representar ocurrencias de una palabra dentro de otra. Las palabras tales que toda a viene seguida de una b no pueden contener aa pero también debemos garantizar que la palabra no termina en a de modo que añadimos esta condición adicional forzando a que termina en b (o que alternativamente es la palabra vacía \lambda).