I have these 2 languages:
$$L_1 = \left\{a^ib^jc^k: k\ge i+j\right\}\\ L_2 = \left\{w_1cw_2 : w_1,w_2\in\{a,b\}^\ast\land |w_1|_a = |w_2|_a\right\}$$
How can I determine that they are context free languages by using the closure properties of context-free languages? Thanks a lot
On
for the first language we have the following context free grammar:
$S \rightarrow aSc | A$
$A \rightarrow bAc | Ac | \lambda$
for the second language we have the following context free grammar:
$S \rightarrow bS | Sb | aSa | c$
which can be proved that constructs the mentioned language(assuming the alphabet is $\{a,b,c\}$).
First we have to assume that at least a language like $K = \{ a^nb^n \mid n\ge 0 \}$ is context-free.
It is possible to construct finite state transducers $T_i$ (i.e., finite state automata with both input and output) sucht that $L_i = T_i(K)$, i.e., $L_i$ is the output of $K$ under transducer $T_i$. Context-free languages are closed under finite state transductions.
As example $T_1$ reads $a$'s and starts outputting $a$'s, but nondeterministically switches to outputting $b$'s. Then, when reading $b$'s it outputs $c$'s. Moreover it may always add extra $c$'s.
If you do not know about finite state transducers, their operation may be replaced by (inverse) morphisms and intersection with regular languages.
You can start with the following idea. Let $h:\{a,b,c\}^*\to \{a,b\}^*$ be defined by $h(a)=a$, $h(b)=a$, and $h(c)=b$, then $h^{-1}(K)$ equals the language $\{ wc^n \mid w\in \{a,b\}^*\text{ and }|w|=n\}$. From that language you can easily make $L_1$ using intersection with a regular language followed by concatenation of $c$'s.