next up previous contents
Siguiente: Monoide de cadenas Un nivel arriba: Fundamentos matemáticos Anterior: Fundamentos matemáticos

Cadenas y lenguajes

El producto cartesiano de dos conjuntos A y B consta de las parejas ordenadas cuyo primer elemento está en A y cuyo segundo elemento está en B. Usaremos la notación de yuxtaposición para denotar al producto cartesiano:

\begin{displaymath}AB=\{ab\vert a\in A,b\in B\}.\end{displaymath}

Cualquier conjunto finito $\Sigma$ es un alfabeto. Entre los alfabetos más comunes están:

\begin{eqnarray*}\mbox{\it Latino\/} &=&\{a,b,c,\ldots,x,y,z\} \\
(0+1) &=&\{0...
...FF)_{16}\} \\
&:& \mbox{\rm s\'\i mbolos del ASCII extendido}
\end{eqnarray*}


Sea $\Sigma^1=\Sigma$ y, para $n\geq 1$, sea $\Sigma^{n+1}=\Sigma \Sigma^{n}$. Cada elemento $\sigma\in\Sigma^{n}$ se dice ser una palabra sobre $\Sigma$ de longitud n. La palabra $\mbox{\it nil\/}$ que no tiene símbolo alguno es la palabra vacía. Definimos $\Sigma^0=\{\mbox{\it nil\/}\}$. El diccionario sobre $\Sigma$ es $\Sigma^*=\bigcup_{n\geq 0}\Sigma^n,$ y, por ende, consta de todas las palabras de longitud finita con símbolos en el alfabeto $\Sigma$. El conjunto de palabras no-vacías, se denota como $\Sigma^+=\Sigma^*-\{\mbox{\it nil\/}\}$. Para cada $n\leq 0$, $\Sigma^{\leq n}=\bigcup_{\nu=0}^n \Sigma^{\nu}$ es el conjunto de palabras de longitud a lo sumo n.

Ejemplos:
1.
$\mbox{\it nil\/}\in\Sigma^*$ para cualquier alfabeto $\Sigma$.
2.
$2000\in\mbox{\it Diez\/}^4\subset\mbox{\it Diez\/}^*$.
3.
$(2000)_2=11111010000\in(0+1)^{11}\subset(0+1)^*$.
4.
$(259430127)_2=1111011101101001011011101111\in(0+1)^{28}\subset(0+1)^*$.
5.
$soyunapalabradetreintayseisliterales\in\mbox{\it Latino\/}^{36}\subset\mbox{\it Latino\/}^*$.
6.
Cualquier programa en C es una palabra en $\mbox{\it ASCII\/}^*$.
Un lenguaje es un subconjunto de cualquier diccionario. $\emptyset$ y $\Sigma^*$ son los lenguajes vacío y total, respectivamente.
next up previous contents
Siguiente: Monoide de cadenas Un nivel arriba: Fundamentos matemáticos Anterior: Fundamentos matemáticos
Guillermo Morales-Luna
2000-06-27