Palabra (matemáticas)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas, una palabra es una sucesión ordenada de elementos tomados de un conjunto fijo de símbolos denominado alfabeto.

Por ejemplo, si X={a,e,i,o,u} es el conjunto alfabeto, todos los siguientes son ejemplos de palabras:

  • aeo
  • ioi
  • aeaeoa
  • uuuu

El número de elementos de una palabra se denomina la longitud de la misma.

Definición formal[editar]

Se define el concepto de palabra como sigue:[1]

Si A es un conjunto, denominado alfabeto, una palabra sobre el alfabeto A es una sucesión a_1,a_2,a_3,\ldots, a_n en que cada entrada a_k es un elemento de A.

A pesar de ser sucesiones, es común listar los elementos concatenados en vez de separarlos por comas. A los elementos del alfabeto también se les denomina los símbolos del alfabeto.

Si \omega=a_1a_2\cdots a_n es una palabra sobre un alfabeto A, al valor de n se denomina la longitud de la palabra y se denota |\omega|. Una palabra de longitud n se denomina una n-palabra (sobre el alfabeto A).

Para cada conjunto alfabeto existe una palabra de longitud cero, denominada palabra vacía, que se denota "" o \varnothing entre otras variantes.

Cuando el alfabeto consta de dos elementos, las palabras reciben el nombre de palabras binarias. En este caso, suele escogerse como alfabeto el conjunto A={0, 1}.

Si \omega = a_1a_2\cdots a_n es una palabra, su palabra reversa es \tilde\omega =a_na_{n-1}\cdots a_1. Una palabra \omega es un palíndromo si \omega=\tilde\omega.

Combinatoria[editar]

Las palabras son un objeto fundamental en el área de combinatoria enumerativa, pues por el principio de la biyección, es posible reducir una gran variedad de problemas a enumerar conjuntos de palabras que cumplan ciertas restricciones.

El resultado básico es el que determina el número de palabras de longitud fija:

El número de palabras de longitud n sobre un alfabeto con r elementos es rn.

La demostración es una consecuencia del principio del producto pues para determinar una palabra hay que realizar n elecciones sucesivas, cada una de las cuales tiene exactamente r formas de realizarse.

A continuación se da un ejemplo clásico de aplicación de palabras a un problema de enumeración.

Un conjunto con n elementos posee 2n subconjuntos distintos.

Demostración
Denotemos por X al conjunto de n elementos al que se desea enumerar los subconjuntos, y listemos los elementos del conjunto en cierto orden: x_1,x_2,\ldots, x_n.

Ahora, cada subconjunto S \subseteq X corresponde a una palabra binaria (sobre el alfabeto A={0,1}) mediante la siguiente regla:

  • La palabra correspondiente a S tiene 1 en la posición k si x_k\in S y tiene 0 en caso contrario.
Para construir la palabra correspondiente a un subconjunto, se coloca un 1 por cada "sí" y un 0 por cada "no".

Por ejemplo, si el conjunto es X=\{a,e,i,o,u\}, con los elementos listados en ese orden, el subconjunto S={a,o,u} corresponde a la palabra 10011:

  • La primera posición es 1 puesto que a está incluido en el subconjunto S.
  • La segunda posición es 0 puesto que e no está incluido en el subconjunto S.
  • La tercera posición es 0 puesto que i no está incluido en el subconjunto S.
  • La cuarta posición es 1 puesto que o está incluido en el subconjunto S.
  • La quinta posición es 1 puesto que u está incluido en el subconjunto S.

De manera similar, cualquier palabra binaria de longitud n corresponde a un subconjunto de X, determinado por las posiciones iguales a 1 en la palabra. Por tanto, la correspondencia entre subconjuntos y palabras es una biyección, de manera que el número de subconjuntos es igual al número de palabras consideradas.

Pero por el teorema básico de conteo de palabras, el número de palabras de longitud n sobre un alfabeto que tiene dos símbolos es precisamente 2^n, por lo que el número de subconjuntos que tiene un conjunto con n elementos es también 2^n.

Estructura algebraica[editar]

Para cada alfabeto fijo A, es posible definir una operación binaria en el conjunto A* de todas las palabras sobre A mediante la operación de concatenación: [2]


Si \omega_1 = a_1a_2\cdots a_n y \omega_2=b_1b_2\cdots b_m son dos palabras, la concatenación de \omega_1 y \omega_2 es la palabra

\omega_1\omega_2=a_1a_2\cdots a_nb_1b_2\cdots b_m

Cuando el alfabeto contiene dos elementos, el monoide libre puede representarse como un árbol binario.

Se puede verificar que la longitud de una concatenación es igual a la suma de las longitudes: |\omega_1\omega_2| = |\omega_1| +|\omega_2|.

La operación de concatenación es asociativa y tiene a la palabra vacía como elemento neutro, por lo que el conjunto A* adquiere estructura de monoide, mientras que el conjunto de palabras no vacías adquiere estructura de semigrupo.,[2] denominados respectivamente monoide libre y semigrupo libre (sobre el alfabeto A).

Una palabra \lambda es un factor de otra palabra \omega si existen palabras \alpha, \beta (posiblemente vacías) tal que \omega = \alpha\lambda\beta. Si \alpha es una palabra vacía, se dice que \lambda es un prefijo de \omega mientras que si \beta es vacía, hablamos de un sufijo.

Es posible representar el monoide libre con una estructura de árbol con la palabra vacía como nodo raíz y en donde los nodos descendientes de \omega son la concatenación de ésta con cualquier elemento del alfabeto.

El conjunto de todas las palabras sobre un alfabeto posee también estructura de conjunto parcialmente ordenado, con el orden denominado orden prefijo dado por la relación {{ecuación|1=\omega\le \tau si \omega es un prefijo de \tau. Este es precisamente el orden cuyo diagrama de Hasse es la representación del monoide descrita en la sección anterior (con la salvead que se dibujaría de abajo hacia arriba, con la palabra vacía en la parte inferior).

Ciencias de la computación[editar]

En ciencias de la computación es común identificar los conceptos de palabra con el de cadena de caracteres, el cual es una sucesión de caracteres o unidades de información, y que constituye uno de los tipos de datos más fundamentales.

Usualmente en computación, los elementos de las cadenas pertenecen suelen ser bytes formando un arreglo que representa, mediante una codificación de caracteres, entidades de información. Por el contrario, en la estructura matemática, el alfabeto subyacente puede ser un conjunto cualquiera (incluso infinito) cuyos elementos no tienen restricción de representación o codificación (los elementos del alfabeto pueden, en teoría, ser incluso otros conjuntos).

Palabras binarias[editar]

Se desea determinar el número de palabras binarias de longitud n. Es decir, series de longitud n formadas por cifras 0 o 1. Por ejemplo, las palabras binarias de longitud 4 son:

0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111

Se debe hacer la observación que estrictamente hablando, una palabra binaria no es lo mismo que un número binario. Una palabra binaria es únicamente una lista formal de símbolos, y por tanto las palabras 0010, 010, 10 son diferentes aunque puedan interpretarse todas ellas como el número binario 10.

Para poder elegir una palabra, es necesario hacer n elecciones, una para cada posición de la palabra. Por ejemplo: la primera posición puede ser 0 o 1 (dos opciones), la segunda posición es independiente de la primera y por tanto puede ser 0 o 1 (dos opciones), y así sucesivamente.

Cada serie de n elecciones corresponde a una palabra y cada palabra corresponde a n elecciones, por lo que el número de palabras binarias es igual al número de formas de realizar n elecciones cada una de las cuales tiene 2 posibilidades. El principio del producto establece entonces que el resultado ha de ser 2\times2\times 2\times \cdots \times 2 = 2^n.


Un argumento similar permite concluir que si se desea enumerar palabras de longitud n, en donde cada posición puede ser cualquiera de r posibles símbolos, el número de formas de hacerlo será r^n.

Ejemplo: Permutaciones[editar]

Referencias[editar]

  1. D.S. Malik; M.K. Sen (2004). Discrete Mathematical Structures. Course Technology. ISBN 0619212853. 
  2. a b M. Lothaire (2002). Algebraic Combinatorics on Words (1st edición). Cambridge University Press. ISBN 0521812208.