4

Given L1 context free non regular language. Given L2 regular language.

Is it possible that L1 U L2 = regular language ? Also, is it possible that L1*L2 = regular language ?

I think that the 2nd one is impossible. But I'm not sure.

Would love to see an example if one of the abovementioned statements (or both) is/are true.

Njol
  • 3,271
  • 17
  • 32
Rouki
  • 2,239
  • 1
  • 24
  • 41

3 Answers3

1

Is it possible that L1 U L2 = regular language ?

Yes, Possible.

A simple case is: if L1 is sub-set of L2 then L1 U L2 will be regular (=L2), for example: L1 : { anbn | where n >= 0 } and L2 = (a + b)*

is it possible that L1 * L2 = regular language ?

No, Concatenation of a context-free and Regular will be context-free (because constraint in pattern of L1 is still there in L1 * L2).

Adding a reference: CS 273: Closure Properties for Context-Free Languages

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • Thanks :) Just if you can answer fast, what kind of language is : L = {a^ib^j | i != j} ? – Rouki Jan 29 '14 at 12:28
  • @Rouki I have already answered this here [Why the need for terminals? Is my solution sufficient enough?](http://stackoverflow.com/questions/15989197/why-the-need-for-terminals-is-my-solution-sufficient-enough/15989998#15989998) It is a CFL – Grijesh Chauhan Jan 29 '14 at 13:41
0

Is it possible that L1 U L2 = regular language ?

Yes, it is possible. But its always better to take an example:

L1 = {0*1*} (regular) and L2 = {0^n1^n |n>=0} (context-free).

L = L1 U L2 = {0*1*} which is regular language but since every regular language is context-free. So, we can say the union of two always results in context-free language.

Is it possible that L1·L2 = regular language ?

the concatenation of a regular and a context-free language always results in a context-free language.Take the above example again:

L = L1·L2 = {(0*1*)·(0^n1^n) |n>=0} (context free).

It can be regular too if for example one of L1 or L2 is Ø, L1·L2 will result in Ø (regular). But since, all regular languages are context-free, Ø is also a context-free.

Check this out: Geeks for Geeks

Deepam Gupta
  • 2,374
  • 1
  • 30
  • 33
-1

yes, Concatenation of a context-free and Regular will be regular

take L1= a^nb^n which is CFL and take L2 = Ø which is regular.

so L1.L2 = (a^nb^n).Ø = Ø which is regular

Note: For concatenation of two language must be regular , there has to be atleast one language to be regular.

roggy
  • 64
  • 1
  • 1
  • 7
  • 1
    You have to prove that the concatenation is regular for *every* possible pair of languages, not just two of your choice. – effeffe Jun 18 '16 at 16:27