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) L²

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

En resumen:

siendo ={0,1}, Lⁿ ^*, tenemos:

4) L⁰ = { w ^* | long(w)=0 } = {}

L¹ = = { w ^* | long(w)=1 } = {0, 1}

L² = { 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:

₂
5) B = L⁰ U L¹ U L² = U L^k = { w

^* | long(w) < 3 }
k=0