Propiedades de lenguajes libre de contexto

Sean $L_1$ y $L_2$ dos lenguajes libres de contexto.

Unión:

$L=L_1\cup L_2$ es libre de contexto, porque podemos construir a partir de las gramáticas $G_1=(\Sigma_T^1,\Sigma_N^1,P^1,\$^1)$ y $G_2=(\Sigma_T^2,\Sigma_N^2,P^2,\$^2)$ con $L_1=L(G_1)$ y $L_2=L(G_2)$ la gramática $G=(\Sigma_T^1\cup\Sigma_T^2,\Sigma_N^1\cup\Sigma_N^2, P^1\cup P^2\cup\{\$\longrightarrow \$^1,\$\longrightarrow \$^2\},\$)$ que es una gramática libre de contexto y obviamente genera todas las palabras tanto en $L_1$ como en $L_2$.

Eso no es el caso si nos limitamos a los lenguajes libres de contexto deterministas.

Concatención:

$L=L_1.L_2$ es libre de contexto, porque podemos construir a partir de las gramáticas $G_1=(\Sigma_T^1,\Sigma_N^1,P^1,\$^1)$ y $G_2=(\Sigma_T^2,\Sigma_N^2,P^2,\$^2)$ con $L_1=L(G_1)$ y $L_2=L(G_2)$ la gramática $G=(\Sigma_T^1\cup\Sigma_T^2,\Sigma_N^1\cup\Sigma_N^2, P^1\cup P^2\cup\{\$\longrightarrow \$^1\$^2\},\$)$ que es una gramática libre de contexto y obviamente genera todas las palabras en $L$.

Eso no es el caso si nos limitamos a los lenguajes libres de contexto deterministas.

Clausura:

$L=L_1^*$ es libre de contexto, porque podemos construir una gramática libre de contexto a partir de la gramática para $L_1$, simplemente añadimos las producciones $\{\$^\prime\longrightarrow \$^\prime\$^\prime,\$^\prime\longrightarrow \$\}$ siendo $\$ el nuevo símbolo inicial.

Intersección:

$L=L_1\cap L_2$ no es libre de contexto (en general), como demuestra el ejemplo: $L_1=\{a^ib^ic^j\;\vert\;i,j>0\}$ y $L_2=\{a^ib^jc^j\;\vert\;i,j>0\}$ nos lleva a $L=L_1\cap L_2=\{a^ib^ic^i\;\vert\;i>0\}$ que no es libre de contexto como ya vimos.

Si confinamos $L_2$ a lenguajes regulares, entonces la intersección produce lenguajes libres de contexto. El argumento es igual de constructivo como en el caso de dos lenguajes regulares.

Complemento:

$L=\overline{L_1}=\mbox{$\Sigma^*$}-L_1$ no es libre de contexto (en general), porque si asumimos que lo fuera y sabiendo que la unión lo es podríamos derivar $\overline{\overline{L_1}\cup\overline{L_2}}=L_1\cap L_2$ como libre de contexto, pero ya sabemos que la intersección no genera siempre tal lenguajes.

Para los lenguajes libres de contexto determinista, el complemento genera un lenguaje libre de contexto determinista, porque es fácil invertir un autómata determinista.

Diferencia:

$L=L_1-L_2$ no es libre de contexto (en general), porque $L=\mbox{$\Sigma^*$}-L_2=\overline{L_2}$ no es libre de contexto.