581 views

if L1 and L2 are not regular language then L1 union L2 is not regular.

this statement is true or false?

my approach is:::

true let suppose L1=  a^n b^n   AND  L2= a^k b^k

both are cfl but if we do union then that also be cfl

and what happened if union is replaced  by concatenation  L1 . L2

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.

FALSE. May or may not Regular.

----------------------------------------------------------

Sigma = {a,b}

L1={ all strings where number of a’s = number of b’s } .

L2 ={all strings where number of a’s ! = number of b’s} .

L1 → Non regular language.

L2 → Non regular language.

L1 U L2 =  Regular.(Complete Language)

Sigma = {a,b}

L1={ a^nb^m | n=m and n,m>=0 } .

L2 ={ a^nb^m | n !=m and n,m>=0 } .

L1 → Non regular language.

L2 → Non regular language.

L1 U L2 = Regular.(a^nb^m | n,m>=0 )

Are there two non-regular languages whose concatenation is regular? - Mathematics Stack Exchange

pumping lemma - Union of two non-regular languages. - Mathematics Stack Exchange

Very nice explanation with a simple example :)
Thanks -:)

@ankit3009 You are in which semester?

Want to connect with me :p I am in 7th Semester. And you are in 5th Sem from Jalpaiguri College I believe :)

As @raja11sep has already covered the part that Non-Reg language  U  Non-Regular language may or may not be Non Regular so I will cover only concatenation part .

Suppose L1 ,L2 and L be some non regular languages .

Let , L1 = L U {e}

L2 = L’ U {e}

(Since L is non regular so L’ is also non regular)

Now L1.L2= (L U {e}).(L’ U {e}) = sigma *  i.e. a regular language

Hence concatenation of two non regular languages may or may not be non regular.

by

Nice Ans.

Here,

1. e= epsilon.

2.(L U {e}).(L’ U {e}) =LL’ U L U L’ U {epsilon} = L U L’ = sigma* (Complete Language).

​​​​​​​3.{a^nb^n}.{c^nd^n}={a^nb^nc^md^m}

An example where, concatenation of two non regular language is non regular.Hence concatenation of two non regular languages may or may not be non regular.

Yes, last year I studied there .

1
470 views
1 vote