3
$\begingroup$

This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some linear $L$ such that $\overline{L}$ is non-linear but still context free?

One attempt I've made was to look at the linear language $L = \{a^nb^ma^ib^j \in (a^+b^+)^2 : n = m \lor i = j\}$ with $$\overline{L} = \overline{(a^+b^+)^2} \cup \{a^nb^m \in a^+b^+: n \neq m\}^2.$$ $\overline{L}$ must be context free since its components are, and the context free languages are closed under $\cup$ and $\circ$. Intuitively $\overline{L}$ doesn't seem linear to me, especially since it contains the contcatenation of linear languages. Maybe the pumping lemma can be used?

Thanks in advance for all help :)

$\endgroup$

1 Answer 1

3
$\begingroup$

It seems you almost solved the problem in your question statement. Note that the $n\neq m$ condition makes pumping hard: one needs a trick using factorials to succeed, see Prove if $L=\{0^m1^n∣m≠n\}$ is regular or not. We use your idea, but start at the other side.

As a shorthand, let $D = a^+b^+a^+b^+ $ be the underlying regular "domain".

Your linked paper by Horváth and Nagy states a pumping lemma for linear-languages, referring to the classic book by Hopcroft and Ullman (page 143, Exercises 6.11 and 6.12). It is interesting to see that this pumping lemma looks exactly like the pumping for context-free languages, but one of its conditions looks more like that for regular languages: we can pump somewhere near the top of the derivation tree.

The example of a non-linear language given there is $L = \{ a^m b^m a^n b^n \mid m,n\ge 1\}$, or
$\{ a^m b^n a^i b^j \mid m=n \text{ and } i=j\}$.

Its complement, $L^c = D^c \cup \{ a^m b^n a^i b^j \mid m\neq n \text{ or } i\neq j\}$ is linear. It can be split into simpler languages, like for example $\{ a^m b^n \mid m> n \}\cdot a^+b^+$.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks a lot for your thorough reply! The example in a paper I linked is really something I should have checked first in hindsight 😅 $\endgroup$
    – Knogger
    Feb 19 at 16:28
  • 2
    $\begingroup$ If someone's wondering how to pump $\overline{L}$ in my question using the trick mentioned by Hendrik Jan, for pumping length $p$ choose $w = a^pb^{p + p!}a^{p + p!}b^p = uvwxy$ and pump $1 + \frac{p!}{n}$ times where $n = \max(|v|, |x|)$. $\endgroup$
    – Knogger
    Feb 19 at 16:30

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.