2
$\begingroup$

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:

If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined over the same alphabet $Σ$ then, the union $L_1∪L_2$ can be a regular language.

I can't find an example to prove that this statement is true because by definition the context-free languages are closed under union operation.

Could someone please provide an example?

$\endgroup$
  • 1
    $\begingroup$ Yes, the result will be context free. Nobody cares. Is it regular though? Some context free languages are, some are not. $\endgroup$ – gnasher729 Jul 24 at 19:27
2
$\begingroup$

Let $L$ be a context-free but not regular language over $\{0,1\}$ such that its complement language $\overline L$ is also context-free. Then $\overline L$ is not regular and $L\cup\overline L=\Sigma^*$ is regular.

In particular, let $L=\{a^nb^n\mid n\in\Bbb N\}$.


The previous example requires you to verify that both $L$ and $\overline L$ are context-free. Here is an example with less burden.

Let $\Sigma=\{a,b,c,d\}$. Let $F_1$ be a context-free but not regular language over $\{a,b\}$. Let $F_2$ be a context-free but not regular language over $\{c,d\}$. Then both $F_1\cup\{c,d\}^*$ and $\{a,b\}^*\cup F_2$ are context-free but not regular. The union of them, $\{a,b\}^*\cup\{c,d\}^*$ is regular.

In particular, Let $F_1=\{a^nb^n\mid n\in\Bbb N\}$ and $F_2=\{c^nd^n\mid n\in\Bbb N\}$.


Exercise 1. If $R$ is a regular language and $F$ is context-free but not regular such that $R\setminus F$ is context-free, then $F\cup (R\setminus F)$ is a desired example. Show that we can take $R=a^*b^*$ and $F=\{a^nb^n\mid n\in\Bbb N\}$.

Exercise 2. If $L_1$ and $L_2$ are 'context-sensitive but not context-free' languages, defined over the same alphabet $Σ$ then, the union $L_1\cup L_2$ can be a context-free language. In fact, the union $L_1\cup L_2$ can be a regular language as well.

$\endgroup$
  • $\begingroup$ Here is another general construction. Let $\Sigma=\{a,b\}$. Let $L$ be a non-regular context-free language over $\Sigma$. Let $L_a = \{\epsilon\}\cup aL \cup b\Sigma^*$ and $L_b = \{\epsilon\}\cup a\Sigma^*\cup bL $. Then both $L_a$ and $L_b$ are non-regular context-free. $L_a \cup L_b = \Sigma^*$. $\endgroup$ – Apass.Jack Jul 25 at 21:06

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.