Are these valid counterexamples to proofs for CF languages with Non-CF complements?

Question

Someone asked for examples of context-free languages with non-context-free complements.

The first answer says:

The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown using the pumping lemma; see here). Its complement $L_2 = \{a,b\}^* \setminus L_1$ is context-free (as shown here).

Maybe in reality this is true, but given the above information, I am not convinced this is a valid example of such a language. I have proved before that $L$ is not CF, so I have no problem accepting that. However, the CFG and proof given for $L_2$ are wrong. I can give a really simple counterexample: when the string $s=aaabaa$. Clearly $s \in L_2$ because it's not of the form $ww$. However, $s$ cannot be constructed using the CFG described for $L_2$.

Proof: The string $s$ is not of the form $A$ or $B$ since the length of the string is even. Therefore it must be of the form $AB$ or $BA$, but this is impossible because both halves of the string have the same character ($a$) in the center. Therefore $s \notin L_2$, which is a contradiction.

The second answer says:

The example you see on Wikipedia: put $A=\{a^n b^n c^m\}$, $B=\{a^m b^n c^n\}$. It's easy to see $\overline{A}$ and $\overline{B}$ are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore $\overline{A} \cup \overline{B}$ is a context-free language with a non-contextfree complement $A \cap B=\{a^n b^n c^n\}$.

This one is even easier to disprove. Sure, deterministic context-free languages are closed under complement, but they're not closed under union. Therefore, the language $\overline{A} \cup \overline{B}$ is not necessarily context free.

I am currently still taking Theory of Computing, so perhaps I've gotten something wrong or overlooked some obvious truth. Can anyone disprove my claims? If not, can you provide a valid example of a CF language with a non-CF complement?

Answer 1

For the first question, $aaabaa$ is generated by the grammar: $$\begin{align*} S&\to AB \\ &\to aB &&\text{using }A\to a\\ &\to aaBa &&\text{using }B\to aBa\\ &\to aaaBaa &&\text{using }B\to aBa\\ &\to aaabaa &&\text{using }B\to b\,. \end{align*}$$ Your attempt to prove the converse is incorrect because you assume that, when the string is split as $AB$, the part generated by $A$ must have the same length as the part generated by $B$. As the derivation above shows, this is not true.

For the second, you're correct that the class of deterministic CFLs is not closed under union. However, the class of CFLs is closed under union. That is, the union of two DCFLs is not necessarily a DCFL but it is definitely a CFL. The argument "$\overline{A}$ and $\overline{B}$ are deterministic context-free, so they are context-free, so $\overline{A}\cup\overline{B}$ is context-free" is implicit in the proof you quote.