Lenguajes

Un lenguaje es cualquier subconjunto del universo sobre algún alfabeto, es decir, $L\subset W(\Sigma)$, o también $L\subset \mbox{$\Sigma^*$}$.

Ejemplo:

• Lenguajes triviales
  • $L=\emptyset$ es el lenguaje vacio (que no contiene ninguna palabra), $\vert L\vert=0$
  • $L=\{\epsilon\}$ es el lenguaje que solamente contiene la palabra vacio, $\vert L\vert=1$
  son independientes del alfabeto y por eso son lenguajes sobre cualquier alfabeto.
• sea $\Sigma=\{a,b\}$
  • $L_1=\{\epsilon,a,b\}$
  • $L_{ab}=\{a^nb^n\;\vert\;n\in\bbbn\}$ es decir, el lenguaje que contiene todas las palabras con un número de $a$s seguidos por el mismo número de $b$s.
  • $L_{pal}=\{ww^R\;\vert\;w\in\mbox{$\Sigma^*$}\}$ es decir, palíndromos
  • $L_{quad}=\{a^{n^2}\;\vert\;n\in\bbbn_{>0}\}$

Si $\vert L\vert<\infty$ para un lenguaje $L\subset \mbox{$\Sigma^*$}$, entonces se llama $L$ lenguaje finito.

Operaciones sobre/con lenguajes, sean $L,L_1,L_2,L_3\subset\mbox{$\Sigma^*$}$ lenguajes (igual para $W(\Sigma)$):

Unión:

$$L_1\cup L_2 = \{ w \;\vert\;w\in L_1 \mbox{ o } w\in L_2 \}$$

Propiedades (unos ejemplos):

Conmutatividad:	$L_1\cup L_2=L_2\cup L_1$
Asociatividad:	$(L_1\cup L_2)\cup L_3 = L_1\cup (L_2\cup L_3)$
Idempotencia:	$L\cup L=L$
Operación con $\emptyset$:	$L\cup\emptyset = L = \emptyset\cup L$
Operación con $\mbox{$\Sigma^*$}$:	$L\cup\mbox{$\Sigma^*$}= \mbox{$\Sigma^*$}= \mbox{$\Sigma^*$}\cup L$

Intersección:

$$L_1\cap L_2 = \{ w \;\vert\;w\in L_1 \mbox{ y } w\in L_2 \}$$

Propiedades (unos ejemplos):

Conmutatividad:	$L_1\cap L_2=L_2\cap L_1$
Asociatividad:	$(L_1\cap L_2)\cap L_3 = L_1\cap (L_2\cap L_3)$
Idempotencia:	$L\cap L=L$
Operación con $\emptyset$:	$L\cap\emptyset = \emptyset = \emptyset\cap L_1$
Operación con $\mbox{$\Sigma^*$}$:	$L\cap\mbox{$\Sigma^*$}= L = \mbox{$\Sigma^*$}\cap L$

Complemento:

$$\overline L = \{ w \;\vert\;w\in \mbox{$\Sigma^*$}\mbox{ y } w\notin L \}$$

Propiedades (unos ejemplos):

Regla de DeMorgan:	$\overline{L_1\cup L_2}=\overline L_1\cap \overline L_2$
	$\overline{L_1\cap L_2}=\overline L_1\cup \overline L_2$

Con estas tres operaciones la estructura $(\mbox{$\Sigma^*$},\cup,\cap,\overline{\;\;})$ forma una álgebra booleana.

Diferencia:

$$L_1-L_2 = \{ w \;\vert\;w\in L_1 \mbox{ pero } w\notin L_2 \}$$

Propiedades (unos ejemplos):

	$\overline L_1=\mbox{$\Sigma^*$}- L_1$
	$L_1-L_2=L_1\cap\overline{\mbox{$\Sigma^*$}\cap L_2)}$

Concatenación:

$$L_1.L_2 = \{ w \;\vert\;w=w_1.w_2\mbox{ y } w_1\in L_1\mbox{ y } w_2\in L_2 \}$$

Propiedades (unos ejemplos):

No-Conmutatividad:	$L_1.L_2\not=L_2.L_1$ (en general)
Operación con $\emptyset$:	$L_1.\emptyset=L_1=\emptyset.L_1$
Operación con $\{\epsilon\}$:	$L_1.\{\epsilon\}=L_1=\{\epsilon\}.L_1$

Potencia:

$$L^i=\underbrace{L \dots L}_{i\mbox{-veces}} \quad i\in\bbbn$$

Propiedades (unos ejemplos):

Cero-Potencia:	$L^0=\{\epsilon\}$
Inducción:	$L^i.L=L^{i+1}=L.L^i$

Clausura positiva:

$$L^+=\bigcup_{i=1}^\infty L^i=L^1\cup L^2\cup L^3\cup\dots$$

Clausura (de Kleene):

$$L^*=\bigcup_{i=0}^\infty L^i=L^0\cup L^1\cup L^2\cup\dots$$

Propiedades (unos ejemplos):

	$L^+=L^*-\{\epsilon\}$
	$\mbox{$\Sigma^*$}=\bigcup_{i=0}^\infty\Sigma^i$

Reflexión (o inverso):

$$L = \{ w \;\vert\;w^R\in L \}$$

Homomorfismo:

Sean $\Sigma, \Gamma$ dos alfabetos. Sea $\varphi:\Sigma\longrightarrow \Gamma^*$ una función que asigna a cada símbolo de $\Sigma$ una palabra sobre $\Gamma$. Podemos ampliar la función $\varphi$ a un homomorfismo $\varphi:\mbox{$\Sigma^*$}\longrightarrow \Gamma^*$, es decir, una función que asigna a cada palabra sobre $\Sigma$ una palabra sobre $\Gamma$, con

$$\begin{eqnarray*} \varphi(\epsilon)&=&\epsilon\\ \varphi(w\sigma)&=&\varphi(w)\varphi(\sigma) \end{eqnarray*}$$

Ejemplo:

$$\begin{eqnarray*} \Sigma&=&\{a,b,c,d\}\\ \Gamma&=&\{0,1\}\\ && \varphi(a)=00\q... ...arphi(c)=\epsilon\quad\varphi(d)=0110\\ \varphi(abcd)&=&0010110 \end{eqnarray*}$$

Entonces si $L\subset \mbox{$\Sigma^*$}$ es un lenguaje sobre $\Sigma$

$$\varphi(L)=\{\varphi(w)\;\vert\;w\in L\}\subset \Gamma^*$$

es un lenguaje sobre $\Gamma$ y si $L\subset\Gamma^*$ es un lenguaje sobre $\Gamma$, entonces

$$\varphi^{-1}(L)=\{w\;\vert\;\varphi^{-1}(w)\in L\}\subset \mbox{$\Sigma^*$}$$

es un lenguaje sobre $\Sigma$.

¿Cuál es el orden de prioridad de estos operadores?