Palabra (matemáticas)

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ónA pesar de ser sucesiones, es común listar los elementos concatenados en vez de separarlos por comas.es una palabra sobre un alfabeto A, al valor de n se denomina la longitud de la palabra y se denotaUna 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 "" oEn este caso, suele escogerse como alfabeto el conjunto A={0, 1}.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.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.Un conjunto con n elementos posee 2n subconjuntos distintos.corresponde a una palabra binaria (sobre el alfabeto A={0,1}) mediante la siguiente regla: Por ejemplo, si el conjunto es= { a , e , i , o , u }, con los elementos listados en ese orden, el subconjunto S={a,o,u} corresponde a la palabra 10011: 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.Se puede verificar que la longitud de una concatenación es igual a la suma de las longitudes: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).es una palabra vacía, se dice queEs 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 deson la concatenación de ésta con cualquier elemento del alfabeto.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).El alfabeto de un lenguaje formal L (que no es otra cosa que un conjunto de palabras) es el conjunto de todas las letras que se usan en L. Es posible considerar lenguajes donde el alfabeto tiene distintas cardinalidades, o incuso que usan palabras infinitas.Por ejemplo, el lenguaje de la lógica de primer orden usa un alfabeto que contiene a las conectivas lógicas, los cuantificadores, una cantidad infinita de variables, el símbolo igual '=' y paréntesis.Es posible que use también símbolos para constantes, funciones y relaciones.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).Por ejemplo, las palabras binarias de longitud 4 son: 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.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 serUn 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á