Let L1 = L2 union L3 find values such that L1 is context free and L2 and L3 are not.

So far I have: L1 = $a^nb^n$ L2 = $a^*b^*$ L3 = $a^+b^+$

Is this acceptable?? Since L2 covers everything including epsilon and L3 is the same but does not include epsilon?

I know L2 is regular so I guess that is also not a CFL. Another problem is that the a's and b's aren't linked in L2 and L3, so either one can always have more a's than b's and vice versa.

  • 4
    $\begingroup$ Every regular language is also a context-free language. $\endgroup$ – kntgu May 13 '18 at 6:35
  • $\begingroup$ There are two problems with your example: first, $L_2$ and $L_3$ are context-free; and second, $L_2 \cup L_3 \neq L_1$. You need to find a different example. $\endgroup$ – Yuval Filmus May 13 '18 at 8:00

Hint. For any language $L$, $$A^* = L \cup (A^* - L).$$ Now, choose an appropriate language $L$ to solve your problem.


Here is another construction: for every language $L$ over $\{0,1\}$, $$ (0L \cup 1\Sigma^*) \cup (1L \cup 0\Sigma^*) = \Sigma^+. $$


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.