selfdoubt

Question

if concatenation of two languages $L_1\ and\ L_2(L_1.L_2)$  is regular then what can we say about $L_1\ and\ L_2 $ ??

is there any possibility of  $L_1=nonregular\ ,\ L_2=nonregular \   $ ?? 

Comments

Are you asking that can both L1 and L2 be nonregular

---

@Shivani gaikawad yeah ,can both L1 and L2 be nonregular??

---

yes possible

both can be CFL

---

@  srestha mam give some example that (nonreg).(nonreg) is regular

---

@Prateek

https://gateoverflow.in/30762/please-give-proper-explanation

---

@srestha mam ,my doubt is different.

---

@Prateek Raghuvanshi
yes, it is possible that both L1 and L2 be non regular
suppose, L1 ={0^prime;prime>=2}
           and, L2 ={0^non-prime;non-prime>=0}
if we concatenate both the languages, we will get L= {0^n;n,>=2} which is regular.

---

Yes it is possible. Consider these two languages

$L1$ = $(a+b)^*a^nb^n(a+b)^*$

$L2$ = $a^mb^m(a+b)^*$

Now when you concatenate then $L1$ can be written as $(a+b)^*$ and also $L2$ can be written as $(a+b)^*$. Now here both are regular language and concatenation of it becomes regular languages

---

@!KARAN

neither L1 is non-regular, nor L2 is non-regular

---

Karan

Range of n and m ??

---

@aambazinga i think your example is perfect!! Nice

---

@Prateek

have u checked point 2)??

intersection and concatenation give  same result

---

@aambazinga you are right but L1.L2 is not 0*.

But yes it is regular.

---

@srestha Yes, the 2nd point in arjun sir's explanation is perfect..

Thank u mam..  :-)

---

@Verma Ashish

I've checked and derived the language too.. it is 0*.

You check it once.

---

@aambazinga how u derive ε,0?

---

@Verma Ashish

Look carefully.. I've said that L2 is 0^non-prime. And epsilon and 0 will be derived from the set L2, which is containing non prime length 0's.

Note: I've not said that L2 is 0^composite... I've said that L2 is 0^non-prime.

---

Ok L2^nonPrime will derive eps and 0 but what if u concatenate with L1?

The smallest string in L1 is 0² so any thing concatenated with L1 would never generate less than 0².

Am i right?

---

Yes, you are right. :D edited.

---

@Aamabazinga good explanation bro:)

Answer 1

Theorem:

Concatenation of two non-regular languages can be regular.

Constructive Proof:

Let $L$ be any non-regular language. Now, we know $L’$ is also non-regular.

Consider $(L \cup \{ \epsilon \})$ ; $(L’ \cup \{ \epsilon \})$, both of which are non-regular.

Now, $(L \cup \{ \epsilon \}).(L’ \cup \{ \epsilon \}) = \Sigma^*$, which is regular.

---

For concrete example:

Consider $L =$ Set of All Prime Numbers over $\{ 0 \}$ , 

$M =$ Set of All Composite Numbers over $\{ 0 \}$

Both $L,M$ are Non-regular.

Now, $L.M = \{ 0^n , n \geq 6 \}$ which is regular.

Answer 2

is there any possibility of  L1=nonregular , L2=nonregular  ?? 

YES!

One can come up with many example but I’ll state one of the standard and easy to understand.

Goldbach's conjecture : It states that every even natural number greater than 2 is the sum of two prime numbers.

L={1^p:p is an odd prime} If the Goldbach conjecture is true then L.L=(11)^+ is regular, but L isn't.