# The complement of a particular language

We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $$L={a^nb^n}$$ is not linear, but I can't prove it.

• Indeed, it is a good challenge to find an example of a linear language, who's complement is not linear. The formulation in Wikipedia if quite indirect. Commented Feb 5 at 15:29
• Hey, I think I might have found a valid counterexample. I've added it to my answer, so please have a look :] Commented Feb 5 at 17:34
• @Knogger Yep. Seems to work. Also the complement of $\{a^nb^nc^n\mid n\ge 0\}$, which is of the same "style" as the language in the question. Commented Feb 5 at 18:11
• @HendrikJan That's a really nice example. Maybe a good heuristic is to look out for context-sensitive languages that can be written as $L = \{x \in L' : \varphi_1(x) \land \varphi_2(x) \land ... \land \varphi_n(x)\}$, and to hope that the summands of $\overline{L} = \overline{L'} \cup \Big(\bigcup_i \{x \in L : \neg \varphi_i(x)\}\Big)$ turn out to be linear. Both languages fit that scheme. Commented Feb 6 at 7:19

The complement of the language $$L = \{a^nb^n : n \in \mathbb{N}\}$$ should actually be linear, if I'm not mistaken. Take some string $$x \notin L$$ over the alphabet $$\Sigma = \{a, b\}$$, since $$L \subseteq a^*b^*$$ one of three cases must be true:

• $$x \notin a^*b^*$$, or
• $$x = a^nb^m \in a^*b^*$$ and $$n > m$$, or
• $$x = a^nb^m \in a^*b^*$$ and $$n < m$$.

So the complement of $$L$$ (relative to $$\Sigma$$) can be expressed as $$\overline{L} = \overline{a^*b^*} \cup \{a^nb^m : n > m\} \cup \{a^nb^m : n < m\}.$$ Now, $$\overline{a^*b^*} \in \texttt{REG}$$ so $$\overline{a^*b^*}$$ must be linear. Using an induction argument over the rules of the linear grammar $$G$$ with rules $$S \to aS | aA$$ $$A \to aAb | \varepsilon$$ and start variable $$S$$, it can be shown that $$L(G) = \{a^nb^m : n > m\}$$ is linear. Similarly, $$\{a^nb^m : n < m\}$$ can be generated by a linear grammar with rules $$S \to Sb | Bb$$ $$B \to aBb | \varepsilon.$$ Since $$\overline{L}$$ can be written as the union of linear languages, and the linear languages are closed under union, it follows that $$\overline{L}$$ must be linear as well.

## Counterexample

I think I might've found a valid counterexample. The language $$L = \{a^nb^mc^k : n \neq m \land m \neq k\}$$ is well known to be context-sensitive.

Observe that $$\overline{L} = \overline{a^*b^*c^*} \cup \{a^nb^mc^k : n = m\} \cup \{a^nb^mc^k : m = k\}.$$ It can be verified that the linear Grammars $$S \to Sc | A$$ $$A \to aAb | \varepsilon$$ and $$S \to aS | A$$ $$A \to bAc | \varepsilon$$ with start variable $$S$$ generate $$\{a^nb^mc^k : n = m\}$$ and $$\{a^nb^mc^k : m = k\}$$ respectively, and that $$\overline{a^*b^*c^*} \in \texttt{REG}$$. So $$\overline{L}$$ is linear whilst $$\overline{\overline{L}} = L$$ is not, counterexample ↯