I need to determine whether L is CF \begin{align} \ L = \{a^nb^kc^n | n,k≥0\}^c \end{align} I think L can be represented by the following union: \begin{align}\ L=L_1\cup\ L_2 \end{align} \begin{align}\ \ L_1 = \{a^nb^kc^m | n≠m\} \qquad L_2 = \{w |w∈\Sigma^*\ , w≠a^*b^*c^*\} \end{align} I just can't find a CFG for L or disprove it using the pumping lemma...
did I get the complement right?
can I get a general direction, is it a CFL or not?
If for word $a^n b^k c^m$ we have $n \neq m$, then either $n > m$ or $n < m$.
In case $n > m$ we can rewrite the word as $a^{n - m} a^m b^k c^m$, and similarly for $n < m$ we can write the word as $a^n b^k c^m$.
Let $A$ generate non-empty sequence of $a$ and $C$ generate non-empty sequence of $c$, and $B$ generate (possibly empty) sequence of $b$.
Now, let make $G$ generate words with $n > m$, $L$ with $n < m$ and $E$ with $n = m$.
It's easy to check that rules $G \to AE$, $L \to EC$, $E \to B$, $E \to aEc$ satisfy these conditions. Adding rules $S \to G$, $S \to L$ we get CFG that generates $L_1$.
And $L_2$ is even regular (as a complement to regular language).