1
$\begingroup$

Let $L_1 = \{a^nb^nc^n\}$ and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure)

So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a CFG.

Is this correct?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! You can use LaTeX to typeset various formulas. I edited to show you how; we also have a brief tutorial. $\endgroup$ – Apass.Jack Nov 1 '18 at 3:07
  • $\begingroup$ The title reads "is ... non context-free" while the body reads " ... is a CFG". Are you saying you have answered your question in the title with the counterexample in the body? $\endgroup$ – Apass.Jack Nov 1 '18 at 3:18
  • $\begingroup$ What do you mean by $i\neq j\neq k$? $\endgroup$ – xskxzr Nov 1 '18 at 3:45
  • $\begingroup$ @Apass.Jack - is my counterexample correct?? Though I am not sure about L2={aibjck∣i≠j≠k} being a non CFL. $\endgroup$ – Achilles Nov 1 '18 at 3:56
  • $\begingroup$ @xskxzr - exponent values of i, j and k will never be same at a time. Hence, at-least 1 value will be different than the other. $\endgroup$ – Achilles Nov 1 '18 at 3:59
2
$\begingroup$

Let $L$ be a non-context-free language over $\{0,1\}$. Then $0L \cup 1\Sigma^*$ and $0\Sigma^* \cup 1L$ are not context-free, but their union $\Sigma^+$ is context-free.

$\endgroup$
2
$\begingroup$

As you suspected, the union of two non context-free languages may be context-free.

For example, $\{a^nb^nc^n\mid n\ge0\}\cup\{a^nb^nc^m \mid m,n\ge 0,m\ne n\,\} = \{a^nb^nc^m\mid m,n\ge0\}$.

For a simpler example, $\{a^{n^2}\mid n\ge 0\}\cup\{a^{m}\mid m \text { is not a square}\} = \{a^{n}\mid n\ge 0\}$.

In fact, by a counting argument on countably infinity, for almost all languages $L$, both $L$ and its complement $\overline L=\Sigma^*\setminus L$ are non context-free (and even non context-sensitive), where $\Sigma$ is the (nonempty) alphabet. Their union, $\Sigma^*$ is context-free (and, actually, regular).


Your example is not correct since $L_3\setminus L_1 = \{a^nb^mc^k\mid n,m,k\ge0, n\ne m\}\cup \{a^nb^mc^k\mid n,m,k\ge0, m\ne k\}$ is a union of two context-free languages, hence also context-free.

$\endgroup$
  • $\begingroup$ Thank you. These examples make more sense. $\endgroup$ – Achilles Nov 2 '18 at 2:38
0
$\begingroup$

$\Sigma^*$ is context free and its union with any language at all is $\Sigma^*$, which is still context-free.

If you want to consider questions about closure properties of languages, always start with things like $\emptyset$ and $\Sigma^*$, which are in any sane class of languages, and very often give give trivial counterexamples to false hypotheses about closure properties. For example, is the union of two non-regular languages always non-regular? No, because it's easy to come up with a language $L$ such that $L$ and $\overline{L}$ are non-regular, but we have $L\cup \overline{L}=\Sigma^*$, which is regular. And, if you wanted intersection instead, $L\cap\overline{L}=\emptyset$ and that's regular, too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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