Álgebra de las palabras

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 conjunto ${displaystyle A_{}^{}}$, es decir, ${displaystyle a,bin A}$, se llama a ${displaystyle <a,b>_{}^{}}$ un par ordenado.

Nota:

Estos pares pueden ser formalmente elementos de nuevos conjuntos sin ningún impedimento, y se pueden comparar con otros pares ordenados ${displaystyle <c,d>_{}^{}}$ exclusivamente en este orden, primero a con c y luego b con d.

Se llama producto cartesiano de dos conjuntos ${displaystyle A_{}^{}}$ y ${displaystyle B_{}^{}}$ al conjunto ${displaystyle A imes B:={<a,;b>:ain A,;bin B}.}$

Dado un conjunto ${displaystyle A_{}^{}}$ y un número natural ${displaystyle ngeq 1_{}^{}}$, se define el conjunto de las sucesiones finitas de longitud n de elementos de ${displaystyle A_{}^{}}$, ${displaystyle A_{}^{n}}$, como el n-ésimo conjunto de la lista siguiente definida por inducción:

${displaystyle {egin{matrix}A^{1}&=&A\A^{2}&=&A imes A\&vdots &\A^{n}&=&A^{n-1} imes A\&vdots &end{matrix}}}$

Se llaman palabras sobre un alfabeto ${displaystyle A_{}^{}}$ al conjunto de las sucesiones finitas de elementos de A definido como el conjunto ${displaystyle A^{ast }=igcup _{ngeq 1}A^{n}}$, 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 ${displaystyle a^{n},b^{n}in A^{n}}$, 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 elementos ${displaystyle a^{m},b^{m+k}in A^{ast }}$ tales que ${displaystyle a_{}^{m}=}$ ${displaystyle <a_{1},;dots ,;a_{m}^{}>=}$ ${displaystyle <b_{1}^{},;dots ,;b_{m+k}>=}$ ${displaystyle b_{}^{m+k}}$ con k>0 y m>1, entonces:

Informalmente es evidente que ${displaystyle a_{1}^{}=}$ ${displaystyle <b_{1},;dots ,;b_{k+1}^{}>}$ debido al resultado anterior para sucesiones de igual longitud, para demostrarlo formalmente se procede del modo siguiente:

Dado un conjunto ${displaystyle A_{}^{}}$ sin elementos expresados mediante sucesiones finitas de sus propios elementos, si ${displaystyle a,bin A_{}^{ast }:a=b}$ entonces:

Se llama operación concatenación entre sucesiones finitas a:

${displaystyle {egin{matrix}circ :&A^{ast } imes A^{ast }&longrightarrow &A^{ast }\&<<a_{1},;dots ,;a_{n}>,<b_{1},;dots ,;b_{m}>>&longmapsto &<a_{1},;dots ,;a_{n}>circ <b_{1},;dots ,;b_{m}>=<a_{1},;dots ,;a_{n},;b_{1},;dots ,;b_{m}>.end{matrix}}}$

Por tanto la estructura ${displaystyle <A^{ast },;circ >}$ es un grupoide libre generado por el conjunto ${displaystyle A_{}^{}}$.

Para hacer referencia al mismo objeto matemático, se escribe por comodidad simplemente ${displaystyle a_{1}dots a_{n}:=}$ ${displaystyle <a_{1},;dots ,;a_{n}>=}$ ${displaystyle <a_{1}>circ cdots circ <a_{n}>.}$