Á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.

El álgebra de las palabras sobre un alfabeto[editar]

Los alfabetos se asocian a conjuntos que pueden ser finitos, numerables de símbolos.

Introducción[editar]

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.

Par ordenado[editar]

Dado un par de elementos de un conjunto $A_{}^{}$ , es decir, $a,b\in A$ , se llama a $<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 $<c,d>_{}^{}$ exclusivamente en este orden, primero a con c y luego b con d.

Producto cartesiano[editar]

Artículo principal: Producto cartesiano

Se llama producto cartesiano de dos conjuntos $A_{}^{}$ y $B_{}^{}$ al conjunto $A\times B:=\{<a,\;b>:a\in A,\;b\in B\}.$

Palabras sobre un alfabeto[editar]

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

${\begin{matrix}A^{1}&=&A\\A^{2}&=&A\times A\\&\vdots &\\A^{n}&=&A^{n-1}\times A\\&\vdots &\end{matrix}}$

Se llaman palabras sobre un alfabeto $A_{}^{}$ al conjunto de las sucesiones finitas de elementos de A definido como el conjunto $A^{\ast }=\bigcup _{n\geq 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:

Los elementos de $A_{}^{1}$ son elementos notados por $x:=<x_{}^{}>$ donde $x\in A.$

Los elementos de $A_{}^{2}$ son pares ordenados, notados como $<a,\;b>:=<<a>,\;b_{}^{}>$ donde $a,b\in A.$

Los elementos de $A_{}^{3}$ son ternas ordenadas, notadas como $<a,\;b,\;c>:=<<a,\;b>,\;c_{}^{}>$ donde $a,b,c\in A.$

En general, para $A_{}^{n}$ se tienen sucesiones finitas de longitud n notadas como $<a_{1},\;\dots ,\;a_{n-1}^{},\;a_{n}>:=$ $<<a_{1},\;\dots ,\;a_{n-1}^{}>,\;a_{n}>$ donde $a_{i}\in A$ , $\forall i\in \{1,\;\dots ,\;n\}.$

Para determinar el contenido de un elemento $a\in A_{}^{n}$ se indica como $a=<a_{1},\;\dots ,\;a_{n}^{}>$ donde $a_{i}^{}$ será el i-ésimo termino de la sucesión.

Esta última notación permite, ya, comparar palabras, son destacables los resultados siguientes:

Sucesiones de igual longitud[editar]

Dado dos elementos $a^{n},b^{n}\in A^{n}$ , entonces

a^{n}=<a_{1},\;\dots ,\;a_{n}>=<b_{1}^{},\;\dots ,\;b_{n}>=b^{n}\Leftrightarrow

a_{i}=b_{i},\;\forall i\in \{1,\;\dots ,\;n\}.

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:

Si n=1, se tiene

<a_{1}^{}>=<b_{1}>

por notación sabemos que

a_{1}^{}=b_{1}.

Si n=2, es decir un par ordenado, se tiene

<a_{1},\;a_{2}>=<b_{1},\;b_{2}^{}>

por comparación de un par ordenado

a_{1}=b_{1}^{}

y

a_{2}=b_{2}^{}.

Supóngase que para el caso n-1 es cierto, véase que también lo es para n, es decir, que es cierto que

a^{n-1}=<a_{1},\;\dots ,\;a_{n-1}^{}>=

<b_{1},\;\dots ,\;b_{n-1}^{}>=b^{n-1}\Leftrightarrow

a_{i}=b_{i},\;\forall i\in \{1,\;\dots ,\;n-1\}

, y ahora se tiene que comprobar para el caso n:

<<a_{1},\;\dots ,\;a_{n-1}>,\;a_{n}^{}>=<<b_{1},\;\dots ,\;b_{n-1}>,\;b_{n}>

, es decir,

<<a^{n-1}>,\;a_{n}>=<<b^{n-1}>,\;b_{n}^{}>

, es decir,

<a^{n-1},\;a_{n}>=<b^{n-1},\;b_{n}^{}>\Leftrightarrow

a^{n-1}=b_{}^{n-1}

y

a_{n}=b_{n}^{}

como se vio en el caso n=2.

Sucesiones de diferente longitud[editar]

Dado dos elementos $a^{m},b^{m+k}\in A^{\ast }$ tales que $a_{}^{m}=$ $<a_{1},\;\dots ,\;a_{m}^{}>=$ $<b_{1}^{},\;\dots ,\;b_{m+k}>=$ $b_{}^{m+k}$ con k>0 y m>1, entonces:

a_{1}^{}=<b_{1},\;\dots ,\;b_{k+1}^{}>

y

a_{i}=b_{i+k}^{}

,

\forall i\in \{1,\;\dots ,\;m\}.

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

Si m=1, se tiene directamente que

a_{1}^{}=

<b_{1},\;\dots ,\;b_{k+1}^{}>

, y por tanto es cierto.

Si m=2, se tiene que

<a_{1}^{},\;a_{2}>=

<<b_{1},\;\dots ,\;b_{k+1}>,\;b_{k+2}>

, como par ordenado, sucede que

a_{1}^{}=

<b_{1},\;\dots ,\;b_{k+1}^{}>.

Supóngase que el caso m-1 es cierto, véase ahora que también lo es para m:

Por hipótesis se puede tomar el par ordenado

<<a_{1},\;\dots ,\;a_{m-1}^{}>,\;a_{m}>=

<<b_{1},\;\dots ,\;b_{(m-1)+k}>,\;b_{m+k}^{}>

, esto prueba la certeza, pues tienen las mismas hipótesis para una k>0 fijada.

Corolario[editar]

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

a y b son de la misma longitud,

$A_{}^{n}\cap A^{m}=\emptyset$ para $n\neq m_{}^{}.$

Concatenación[editar]

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

${\begin{matrix}\circ :&A^{\ast }\times 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 $<A^{\ast },\;\circ >$ es un grupoide libre generado por el conjunto $A_{}^{}$ .

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