Mostrando que los 2 idiomas son libres de contexto

Question

Tengo estos 2 idiomas:

$$L_1 = \left{a^ib^jc^k: k\ge + j\right} \ L_2 = \left{w_1cw_2: w_1, w_2\in\ {a, b} ^ \ast\land | w_1 | _a = | w_2 | _a\right} $$

¿Cómo puedo determinar que son lenguajes libres de contexto mediante las propiedades de cierre de idiomas context-free? Muchas gracias

(Captura de pantalla original de fórmulas)

Answer 1

En primer lugar tenemos que asumir que, al menos, una lengua como el $K = \{ a^nb^n \mid n\ge 0 \}$ es independiente del contexto.

Es posible construir transductores de estados finitos $T_i$ (es decir, autómatas de estado finito con tanto de entrada como de salida) sucht que $L_i = T_i(K)$, es decir, $L_i$ es el resultado de $K$ bajo transductor $T_i$. Contexto libre de idiomas son cerrados bajo de estado finito transductions.

Como ejemplo, $T_1$ lee $a$'s, y se inicia la salida de $a$'s, pero nondeterministically cambia a la salida de $b$'s. Entonces, cuando la lectura de $b$'s salidas de $c$'s. Además siempre puede agregar adicional $c$'s.

Si usted no sabe acerca de transductores de estados finitos, su operación puede ser reemplazado por (inversa) morfismos y la intersección con el ordinario de idiomas.

Usted puede comenzar con la siguiente idea. Deje $h:\{a,b,c\}^*\to \{a,b\}^*$ ser definido por $h(a)=a$, $h(b)=a$, y $h(c)=b$, a continuación, $h^{-1}(K)$ es igual al lenguaje $\{ wc^n \mid w\in \{a,b\}^*\text{ and }|w|=n\}$. A partir de ese idioma que usted puede hacer fácilmente $L_1$ el uso de intersección con un lenguaje regular, seguido por la concatenación de $c$'s.

Answer 2

para la primera lengua contamos con el siguiente contexto libre de gramática:

$S \rightarrow aSc | A$

$A \rightarrow bAc | Ac | \lambda$

para la segunda lengua tenemos el siguiente contexto libre de gramática:

$S \rightarrow bS | Sb | aSa | c$

que puede ser demostrado que construye el lenguaje mencionado (suponiendo que el alfabeto es ${a,b,c}$).