El álgebra de las palabras estudia la formalización gramatical de las construcciones de palabras sobre un alfabeto para un lenguaje, desde una perspectiva matemática que permita, de un modo firme, afirmar o rechazar diversos resultados necesarios para fundamentar cualquier modelo matemático de un lenguaje, y más inmediatamente el lenguaje proposicional.Los alfabetos se asocian a conjuntos que pueden ser finitos, numerables de símbolos.La notación matemática utilizada es la desarrollada en teoría de conjuntos, por lo que requiere una base mínima para un rápido trabajo y asimilación con simplicidad y fluidez de los nuevos conceptos.Para introducir nociones que permitan unir símbolos se necesita las siguientes definiciones.Dado un par de elementos de un conjuntoa , b ∈, se llama a< a , b{\displaystyle _{}^{}}Nota: Estos pares pueden ser formalmente elementos de nuevos conjuntos sin ningún impedimento, y se pueden comparar con otros pares ordenados< c , d{\displaystyle _{}^{}}exclusivamente en este orden, primero a con c y luego b con d. Se llama producto cartesiano de dos conjuntosal conjuntob >: a ∈y un número natural, se define el conjunto de las sucesiones finitas de longitud n de elementos de, como el n-ésimo conjunto de la lista siguiente definida por inducción:Se llaman palabras sobre un alfabetoal conjunto de las sucesiones finitas de elementos de A definido como el conjunto, es decir, las palabras son por definición una colección de todas las sucesiones finitas de elementos de un mismo alfabeto.Notaciones: Esta última notación permite, ya, comparar palabras, son destacables los resultados siguientes: Dado dos elementos, entonces No es necesario definirlo así, pues se puede demostrar a partir de las definiciones que ya se tiene, la demostración habitual, para sucesiones, es comparando los elementos ordenadamente según existan, es decir, mediante inducción: Dado dos elementoscon k>0 y m>1, entonces: Informalmente es evidente quedebido al resultado anterior para sucesiones de igual longitud, para demostrarlo formalmente se procede del modo siguiente: Dado un conjuntosin elementos expresados mediante sucesiones finitas de sus propios elementos, sientonces: Se llama operación concatenación entre sucesiones finitas a:{\displaystyle {\begin{matrix}\circ :&A^{\ast }\times A^{\ast }&\longrightarrow &A^{\ast }\\&<,>&\longmapsto &\circ =.\end{matrix}}}es un grupoide libre generado por el conjuntoPara hacer referencia al mismo objeto matemático, se escribe por comodidad simplemente
