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:

$$AB=\{ab\vert a\in A,b\in B\}.$$

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.
Siguiente: Monoide de cadenas Un nivel arriba: Fundamentos matemáticos Anterior: Fundamentos matemáticos