1,140 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

3 Answers

Best answer
1 votes
1 votes

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.

My answer here: https://cs.stackexchange.com/a/156523/132177 

edited 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

 

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.

Related questions

0 votes
0 votes
3 answers
1
vishal8492 asked Dec 4, 2016
589 views
It seemed like , this is textbook example of non-CFL language ; will require 2 comparisons . That means no complement exist was the answer , I was expecting. Why answer g...
1 votes
1 votes
2 answers
2
vishal8492 asked Dec 2, 2016
1,375 views
Isn't WxWr DCFL as X acts as marker so DCFL should be right choice , why is it categorized as CFL and not DCFL?
1 votes
1 votes
2 answers
3
Parshu gate asked Dec 10, 2017
746 views
LC may be CFL LC cannot be CFL LC may be regular LC may or may not be CFL
5 votes
5 votes
1 answer
4
Parshu gate asked Nov 16, 2017
671 views
Let L={ai bj ck ┤|if j is odd then i=k} where i,j,k>0. Which of the following option is true about L? L is CSL but not CFL L is CFL but not DCFL L is regular L is D...