in Theory of Computation
581 views
2 votes
2 votes

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

in Theory of Computation
581 views

3 Answers

1 vote
1 vote
Best answer

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.

selected by
5 votes
5 votes

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

 

4 Comments

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

@ankit3009 You are in which semester?

0
0

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

1
1
3 votes
3 votes

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.

2 Comments

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.

1
1
Yes, last year I studied there .
0
0

Related questions