Alfabetos, cadenas y lenguajes

Definición 2.1   Un alfabeto es un conjunto finito no vacío de símbolos y se denota como $\Sigma$.

La pertenencia de un símbolo $\sigma$ a un alfabeto $\Sigma$ se denota como $\sigma$ $\in$ $\Sigma$.
Ejemplo: Podemos representar el alfabeto de las letras minúsculas que utiliza el idioma español, el cual contiene los 27 símbolos siguientes:

$$\Sigma = \left\{ a,b,c,d,e,f,g,h,i,j,k,l,m,n,\textrm{\~n},o,p,q,r,s,t,u,v,w,x,y,z\right\},$$

y sabemos que la letra $a$ pertenece a este alfabeto, lo cual denotaremos como $a\in\Sigma$.
Ya sabemos que los alfabetos son conjuntos, por lo que, todas las operaciones de conjuntos se pueden aplicar a los alfabetos también. Sean $\Sigma_1,\Sigma_2, \ldots, \Sigma_n$ alfabetos, y ya que los alfabetos son conjuntos finitos, no vacíos, la unión de un número finito de ellos $\bigcup_{i=1}^n \Sigma_i$ resulta en un conjunto no vacío y finito, esto es, si $\Sigma_{i}\neq\emptyset$ y $\Sigma_{i+1}\neq\emptyset,\ \mathrm{entonces} \ \Sigma_{i}\cup\Sigma_{i+1}\neq\emptyset.$
La unión de un número arbitrario finito de alfabetos resultará en un conjunto finito y no vacío, es más, si $\Sigma_1$ y $\Sigma_2$, son conjuntos no vacíos, entoces $\Sigma_1 - \Sigma_2, \ \Sigma_2 - \Sigma_1\ \textrm{y}\ \Sigma_1\cap\Sigma_2$ son conjuntos finitos, no vacíos, y por lo tanto serán considerados alfabetos válidos.

Definición 2.2  

Una cadena o palabra es una secuencia finita de símbolos que pertenecen a un alfabeto y comunmente se denota con la letra $w$. La cadena vacía se denota como $\varepsilon$ y es una secuencia vacía de símbolos tomados de cualquier alfabeto $\Sigma$.

Sí el alfabeto es el español, algunas cadenas pueden ser $yomero$, $tumero$ y $malnacido$. Dada la definición anterior, cualquier palabra que contenga los símbolos del alfabeto es una cadena válida, sin importar si esta tiene o no significado alguno.
Si $w$ es cualquier cadena, su longitud se denota como $\vert w\vert$, la longitud de una cadena es el número de símbolos que contiene, por ejemplo, si tenemos la cadena $w=malnacido$ sobre el alfabeto español, $\vert w\vert=9$. La cadena vacía $\varepsilon$ no tiene símbolos, por lo que $\vert\varepsilon\vert=0$

Definición 2.3  

Un lenguaje $L$ es un conjunto de cadenas sobre un alfabeto $\Sigma$ definido, éstas pueden ser cualquier cadena $w$, que cumpla con lo siguente, $w$ esta formada por los símbolos $\sigma_1\sigma_{2}\ldots\sigma_{k}$ donde $\sigma_k \in \Sigma\ \forall k$.

El lenguaje vacío es aquel que no contiene cadenas y no es lo mismo que el lenguaje formado por la cadena vacía $\{\varepsilon\}$, éste lenguaje se denota de la misma manera que el conjunto vacío, $\emptyset$.
Sí se tiene una cadena $w$ sobre un alfabeto $\Sigma$ y $L$ es el lenguaje compuesto por algunas de las cadenas sobre el alfabeto $\Sigma$ y $w \in L$, entonces diremos que $w$ es un miembro de $L$.

Definición 2.4   Un lenguaje universal sobre algún alfabeto $\Sigma$, o cerradura de $\Sigma$, es el lenguaje que contiene todas las cadenas que es posible formar con los símbolos de $\Sigma$ y se denota como $\Sigma^*$.

Ejemplo: Sea $\Sigma=\{a\}$, entonces $\Sigma^*=\{\varepsilon,a,aa,aaa,\ldots\}.$

Podemos observar que para cualquier alfabeto $\Sigma$, $\Sigma^*$ es infinito, ya que los alfabetos son conjuntos no vacíos.