Conjuntos de Palabras


Una palabra es una secuencia finita ordenada de caracteres unidos sin espacios.

Al conjunto de caracteres disponibles para formar palabras se denomina alfabeto .


Ejemplo: Sea ={0,1}, luego podemos tener un conjunto infinito de palabras * a partir de los elementos del alfabeto , cuyas palabras pueden ser desde un bit hasta el programa más grande jamás escrito, e.g. 101, 110101, 110101001, etc.

Podemos tener un conjunto finito de palabras denominado lenguaje L que sea subconjunto de *, es decir:

L *

Suponga que sea

1)    L = { 00, 01, 10, 11 }

Otra forma de definirlo puede ser

2)    L = { w * | long(w)=2 }


donde w es una variable que representa a cualquier palabra binaria que satisfaga la condición long(w)=2, es decir, cuya longitud sea igual a dos caracteres.



Lo mismo puede especificarse mediante:

3)    L2

donde el superíndice indica que las palabras binarias en L deben contener una longitud igual a dos caracteres.



En resumen:


siendo ={0,1},   Ln *, tenemos:

4) L0 = { w * | long(w)=0 } = {}

     L1 = = { w * | long(w)=1 } = {0, 1}

     L2 = { w * | long(w)=2 } = {00,11,10,11}

     donde:
               =  palabra vacía




En cambio, si deseamos especificar un lenguaje que acepte palabras binarias hasta una longitud igual a tres dígitos (combinación de los conjuntos anteriores) tenemos:

                                     2
5) B = L0 U L1 U L2 = U Lk = { w * | long(w) < 3 }
                                   k=0




Terminología



Palabra = cadena = símbolo terminal, e.g. abc.
Convenciones: se identifican usando las primeras letras del alfabeto en monoespacio.


Caracter = letra = símbolo, e.g. a,$,+,if, etc.
Es un elemento del conjunto-alfabeto .
Nota: Un símbolo puede estar formado por más de un elemento.


Conjunto Alfabeto de caracteres . (sigma).
Delimita el universo disponible de caracteres para construir palabras en un lenguaje dado.


Cerradura de Kleene, e.g. * (sigma-estrella).
Representa todas las palabras posibles que pueden formarse con los caracteres del alfabeto , incluyendo la
palabra vacía.
         
* = U k
          k=0

Cerradura Positiva, e.g. + (sigma-positiva). Semejante a *, excepto que no incluye la palabra vacía.
         
+ = U k
          k=1

Palabra vacía o nula = cadena vacía. Palabra especial carente de letras y con longitud igual a cero.
Convención: Se denota por el símbolo .
Variables para palabras.
Notación abstracta cuyo valor representa cualquier palabra válida de un lenguaje dado, e.g. w,x,y,z.
Convención: Se identifican con las últimas letras del alfabeto en itálicas.


Alberto Pacheco
http://www.socrates.itch.edu.mx/~apacheco/teoria/setw.htm
Ultima actualización: Mzo 5, 1999