Siguiente: Ejercicios Un nivel arriba: Propiedades de lenguajes Anterior: Algunas variantes

Propiedades de cerradura

Una clase de lenguajes ${\cal L}$ es un álgebra si es cerrada por unión y complemento y si contiene al conjunto vacío. Es decir, si se cumplen las propiedades

$$\begin{eqnarray*}&& \emptyset \in {\cal L}\\ L \in {\cal L} &\Rightarrow& L^c=... ... L_1,L_2 \in {\cal L} &\Rightarrow& L_1 \cup L_2 \in {\cal L} \end{eqnarray*}$$

En una clases de lenguajes, además de caracterizar la solubilidad de los problemas de la palabra y de derivación, mencionados en la Introducción del curso, también es importante decidir si acaso una clase dada de lenguajes en un álgebra. Por ejemplo, la clase de lenguajes regulares sobre un alfabeto finito forma un álgebra de conjuntos. La clase de lenguajes recursivamente enumerables, es decir, aquellos que son generados por gramáticas irrestrictas, contiene al conjunto vacío, y la unión y la intersección de cualesquiera dos lenguajes en la clase están en la clase, sin embargo no ocurre lo mismo para la operación de complementación. En general, si $\Phi$ es un operador de aridad k, que transforma k lenguajes dados en algún otro lenguaje, un problema importante para una clase ${\cal L}$ de lenguajes es decidir cuándo esa clase es cerrada bajo el operador, es decir, cuándo rige la implicación:

$$L_1,\ldots,L_k\in {\cal L}\ \Rightarrow\ \Phi(L_1,\ldots,L_k) \in {\cal L}.$$

La siguiente observación se sigue inmediatamente de las conocidas Leyes de De Morgan, válidas en el álgebra de conjuntos:

Observación 3.1   Una clase de lenguajes ${\cal L}$ es un álgebra si y sólo si

1.

contiene al lenguaje vacío, $\emptyset$,

2.

es cerrada bajo la unión, y

3.

es cerrada bajo la operación de complementación.

Hemos ya visto algunos de los operadores más usuales entre lenguajes:

Unión.

$L_1+L_2=L_1\cup L_2=\{\sigma\vert(\sigma\in L_1)\mbox{\rm o }(\sigma\in L_2)\}$: palabras que están en L₁ o en L₂.

Intersección.

$L_1\cap L_2=\{\sigma\vert(\sigma\in L_1)\mbox{\rm y }(\sigma\in L_2)\}$: palabras que están en ambos lenguajes L₁ y L₂.

Diferencia.

$L_1-L_2=\{\sigma\vert(\sigma\in L_1)\mbox{\rm pero }(\sigma\not\in L_2)\}$: palabras que están en L₁ pero no en L₂.

Complemento.

$L^c=\Sigma^*-L$: palabras en el diccionario que no están en L.

Concatenación.

$L_1\cdot L_2=\{\sigma\vert\exists \sigma_1\in L_1, \sigma_2\in L_2:\sigma=\sigma_1\cdot\sigma_2\}$: palabras formadas al concatenar partículas en L₁ y en L₂.

0-ésima potencia.

$L^0=\{\mbox{\it nil\/}\}$: mónada consistente de la palabra vacía.

m-ésima potencia (m>0).

$L^m=\{\sigma\vert\exists \sigma_1,\ldots,\sigma_m\in L:\ \sigma=\sigma_1\cdots\sigma_m\}$: palabras que se forman al concatenar m partículas en L.

Operador ``estrella'' (de Kleene).

$L^*={\displaystyle \bigcup_{n\geq 0} L^n}$: palabras que se forman al concatenar un conjunto finito de partículas en L, incluída la palabra vacía.

Operador ``más''.

$L^+={\displaystyle \bigcup_{n>0} L^n}=L^*-L^0$: palabras que se forman al concatenar un conjunto finito de partículas en L.

Mas también los siguientes serán utilizados en este curso:

i-ésima m-ava parte.

A cada palabra del lenguaje se la divide en partes iguales y se toma la i-ésima:

$$\left(i,\frac{1}{m}\right)L=\{\sigma_i\vert\forall j\in([\![1... ...ng}(\sigma_i)\ \&\ \sigma_1\cdots\sigma_i\cdots\sigma_m\in L\}:$$

palabras que se forman al ``dividir'' en m partes de igual longitud a palabras en L, $1\leq i\leq m$.

m-ésimas repeticiones.

$L^{(m)}=\{\sigma\vert\exists \sigma_1\in L:\ \sigma=\sigma_1^m\}$: palabras que se forman al concatenar m copias de una misma partícula en L.

Raíz m-ésima.

$\sqrt[m]{L}=\{\sigma\vert \sigma^m\in L\}$: palabras tales que al concatenar m copias de ellas producen una palabra en L. Por tanto, $L=\left(\sqrt[m]{L}\right)^{(m)}$.

Cociente izquierdo.

$L_1\backslash L_2 = \{\sigma\vert \exists\sigma_2\in L_2: \sigma\sigma_2\in L_1\}$: prefijos que con sufijos en L₂ dan palabras en L₁.

Derivada izquierda.

$\partial_{\tau}^{\mbox{\scriptsize\it izq}}(L) = L\backslash \{\tau\}= \{\sigma\vert \sigma\tau\in L\}$: prefijos que con $\tau$ dan palabras en L.

Cociente derecho.

$L_1/ L_2 = \{\sigma\vert \exists\sigma_2\in L_2: \sigma_2\sigma\in L_1\}$: sufijos que con prefijos en L₂ dan palabras en L₁.

Derivada derecha.

$\partial_{\tau}^{\mbox{\scriptsize\it der}}(L) = L/ \{\tau\}= \{\sigma\vert \tau\sigma\in L\}$: sufijos que con $\tau$ dan palabras en L.

Reverso.

$L^{\mbox{\scriptsize\it rev}}= \{\sigma^{\mbox{\scriptsize\it rev}}\vert \sigma\in L\}$.

Siguiente: Ejercicios Un nivel arriba: Propiedades de lenguajes Anterior: Algunas variantes