Palabras

Una secuencia finita de símbolos de un alfabeto es una palabra sobre dicho alfabeto.

$$\begin{eqnarray*} \Sigma_1 &:& 0, 1, 00, 01, 11, 000, 1001101 \\ \Sigma_2 &:& a... ...m{napa}, \mathrm{palabra}\\ \Sigma_6 &:& a, ab, aab, aaab, abab \end{eqnarray*}$$

Escribimos la palabra vacía, es decir, la palabra que no contiene ningún símbolo, como $\epsilon$.

• Usamos normalmente letras minúsculas para anotar palabras, preferiblemente desde el final del alfabeto.
• El símbolo $\epsilon$ no pertenece a ningún alfabeto, $\epsilon\notin\Sigma$

La longitud de una palabra sobre un alfabeto es el número de símbolos que contiene.

$$\begin{eqnarray*} \Sigma_1 &:& w=0 \Longrightarrow \vert w\vert=1, \quad w=10011... ... w=aab \Longrightarrow \vert w\vert=1 \;o\; \vert w\vert=2\;\;?? \end{eqnarray*}$$

• Dependiendo del alfabeto puede resultar difícil dividir una palabra en sus símbolos.
• Si se puede dividir todas las palabras sobre un alfabeto solamente de una manera en sus símbolos, se llama tal alfabeto libre.
• Solemos usar solamente alfabetos libres.
• $\vert\epsilon\vert=0$

El conjunto de todas las palabras que se pueden formar sobre un alfabeto $\Sigma$ más la palabra vacía se llama el universo del alfabeto $W(\Sigma)$.

• $W(\Sigma)=\{\epsilon\}\cup\{w\;\vert\;w \mbox{ es palabra sobre } \Sigma\}$
• $\Sigma \subset W(\Sigma)$
• $\epsilon$ es palabra de cualquier universo, $\epsilon\in W(\Sigma)$.
• La cardinalidad del universo es infinito (pero contable o enumerable, vemos más adelante lo que significa).
• Si el alfabeto es libre (o mejor decir, un generador libre), escribimos $\Sigma^*$ por $W(\Sigma)$.

Podemos concatenar palabras, entonces sean $w$, $v$ y $u$ palabras en $\Sigma^*$.

• $w.v = wv$, es decir, usamos el $.$ como símbolo de concatenación, pero muchas veces obviamos de él (igual como se suele hacer con el $\cdot$ de la multiplicación).
• $\epsilon w=w=w\epsilon$, es decir, $\epsilon$ se comporta como el elemento neutro (o elemento de intentidad) respecto a la concatenación.
• $\vert w.v\vert=\vert w\vert+\vert v\vert$
• $w.v\not= v.w$ para cualquier $w$ y $v$, por ejemplo:
  
  $$w=abc\quad v=dec \qquad wv=abcdec\not= decabc=vw$$
  
  
  es decir, la concatenación no es conmutativa.
• $(w.v).u=w.(v.u)$ para cualquier palabras $w$, $v$ y $u$, por ejemplo:
  $$\begin{eqnarray*} w=abc\quad v=dec \quad u=fad \\ (wv)u=(abcdec)fad=abcdecfad=abc(decfad)=w(vu) \end{eqnarray*}$$
  
  
  es decir, la concatenación es asociativa (usamos arriba las paréntesis como metasímbolos).
• Con dichas propiedades la estructura algebraica $(\Sigma^*,\;.\;)$ forma un monoide libre (es decir, un semigrupo con elemento de intentidad).

Si $xy=w$, llamamos $x$ prefijo de $w$ e $y$ sufijo de $w$.

• Por $\epsilon w=w$ y $w\epsilon=w$, $\epsilon$ es por lo tanto prefijo y sufijo (trivial) de cualquier palabra, y $w$ es prefijo y sufijo trivial de si mismo. (Normalmente no consideramos estos casos triviales.)
• Si $x$ es prefijo de $w$ entonces $\vert x\vert\leq \vert w\vert$.
• Si $y$ es sufijo de $w$ entonces $\vert y\vert\leq \vert w\vert$.
• Si $x$ es prefijo de $w$, e $y$ es sufijo de $w$ y $x=y$, entonces $x=y=w$, ¿es verdad?

Si concatenamos siempre la misma palabra $w$, obtenemos potencias de $w$.

• $ww=w^2$, $\quad www=w^3$, $\quad \underbrace{w \dots w}_{i\mbox{\small -veces}}=w^i$, $i\in\bbbn=\{0,1,2,\cdots\}$
• $w^1=w$, $\quad w^0=\epsilon$
• $\vert w^i\vert=i\cdot\vert w\vert$
• $\vert w^0\vert=\vert\epsilon\vert=0=0\cdot\vert w\vert=\vert w^0\vert$
• $w^{m+n}=w^m.w^n$
• $\vert w^{m+n}\vert=(m+n)\cdot\vert w\vert=m\cdot\vert w\vert+n\cdot\vert w\vert=\vert w^m\vert+\vert w^n\vert$

La reflexión de una palabra $w$ (o la palabra reversa) anotamos como $w^R$.

• $\vert w\vert=\vert w^R\vert$
• $\epsilon=\epsilon^R$