Redirected
3,475 views
1 votes
1 votes
Let $L_1$ and $L_2$ be languages over $\Sigma$ and assume that $L_1 \cap L_2 = \phi$. if $L_1$ is finite language and $L_1 \cup L_2$ is regular then $L_2$ is ____ ?

a. Regular language and finite

b. Regular language and infinite

c. Need not be regular

d. None of these

3 Answers

Best answer
5 votes
5 votes
Let L2 = compl(L1). Now, L1 intersect L1 is empty and L1 union L2 is ∑* and hence regular. And L2 here is regular and infinite - so A option is eliminated.

Now, we have L1 union L2 as regular and hence we have a DFA (say D) for it. We also have DFA for L1 (say D1). Now, we can make a DFA for L2 (say D2) by doing D intersect compl(D1), as complement of a regular language is regular and regular set is closed under intersect. So, L2 must be regular.

Now, consider L2 = {}. Now, L1 intersect L2 is empty and L1 union L2 is L1 which is regular. But here, L2 is regular and finite.

Hence option D- none of these.
selected by
1 votes
1 votes
As L1 is regular and  L1⋃L2 is regular then L2 must be regular as RL are closed under Union. But we can't say whether L2 is finite or infinite bcz it may be or may not be finite... Correct me if I am wrong
0 votes
0 votes
Although I Arjun sir has answered this question still I’m trying a kind of a different approach correct me if I’m wrong….okay so it is given that L1 and L2 are two languages over the same sigma and L1 intersection L2 is phi i.e they have nothing in common and L1 U L2 is regular and L1 is a finite language i.e it is regular.

The first option is Regular and Finite which is incorrect as if we consider this L1={a} and L2={b(a^n)|n>=0} then also L1 inter L2 = phi and L1 U L2 is regular and L1 is finite.

Option b is incorrect as if we say L1={a} and L2={b} then also the conditions are satisfied but L2 is a regular and finite language

Option C says need not be regular so let us take L2 to be a CFL that satisfies the condition L1 inter L2=phi and L1UL2=reg which is impossible as L1 is a finite language and for L2 to be a CFL and not regular it must be infinite then even the most basic CFL a^n b^n |n>=0 will not hold the union property because union of these two can never be regular.

So the remaining option is D which is correct...anyways here L2 must be regular finite infinite doesn’t matter but L2 has to be regular for all the conditions to be true.

Related questions

0 votes
0 votes
0 answers
1
Gate Fever asked Oct 13, 2018
143 views