1,419 views
0 votes
0 votes
For the following question if True show why, and if it’s False show why.)

Question: For any language A1, A2, if $A1 \cup A2$ is regular, then A1 and A2 are regular languages.
 

I think this is false, but I'm stuck on showing/proof in it. Any help or tips is appreciated.

3 Answers

Best answer
1 votes
1 votes
If L1UL2 is regular then L1 and L2 must be regular is the wrong statement as

 

L1=sigma* is regular

L2={a^nb^n | n>=0} is non regular

But L1UL2 is regular .

 

Hence proved
selected by
1 votes
1 votes
If L1UL2 is regular then L1 and L2 must be regular(always not True)
Let L1 be regular: $(a+b)^*$

L2 be Cfl: $a^nb^n$

$L{_1}\cup L{_2} = (a+b)^*$
0 votes
0 votes
None can be regular still the union of both can be regular.

L1: { anbn | n>=0 }

L2: { ambn | m!=n U All strings having
       substring 'ba' }

Please note L2 is CFL. Why?

L2 is union of two languages.{ ambn | m!=n } which is CFL. And, All strings with 'ba' as substring(this is regular, you can make a DFA for this language)

We know that CFLs are closed in union with regular. ie Regular U CFL is CFL.

Therefore L2 is CFL(but not regular).

Remember all regular languages are also CFLs. But not the opposite way. One way theorem.

Please also note that L2 is complement of L1.

Hence so far,

             L1 is CFL. L2 is CFL.

             L1 is complement of L2.

Therefore, L1 U L2 is universal set (a+b)*. Which is regular. Because L U L(complement) is universal.

Hence for a union of two language L1 and L2 to be regular. None on L1 and L2 needs to be regular.

Related questions

1 votes
1 votes
1 answer
4