2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Commented Feb 5 at 15:29
  • $\begingroup$ Hey, I think I might have found a valid counterexample. I've added it to my answer, so please have a look :] $\endgroup$
    – Knogger
    Commented Feb 5 at 17:34
  • $\begingroup$ @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. $\endgroup$ Commented Feb 5 at 18:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Knogger
    Commented Feb 6 at 7:19

1 Answer 1

3
+50
$\begingroup$

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 ↯

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.