2,237 views
1 votes
1 votes
Prove or disprove the following statement: The union of a regular language with a disjoint non-regular language over the same alphabet can never be regular.

2 Answers

Best answer
7 votes
7 votes
Let $L_1$ be regular and $L_2$ be non-regular and $L_1 \cap L_2 = \emptyset$. Assume $L_1 \cup L_2 $ is regular. Now, we have a DFA for $L_1 \cup L_2$ and also for $L_1$. So, to check if a string belongs to $L_2$,  we have to make a DFA for $\bar{L_1} \cap (L_1 \cup L_2)$ which equals $L_2.$ $\bar{L_1}$ is regular as regular languages are closed under complement. And intersection of two regular languages is regular as regular languages are closed under intersection too. Thus we get $L_2$ as regular which is not possible. So, $L_1 \cup L_2$ cannot be regular.
selected by
1 votes
1 votes
True.

Let us assume given statement is true.

Suppose L1 is a regular language and L2 is a non-regular language, such that L1∩L2=Φ

⇒ L1 U L2 must be regular.

⇒(L1 U L2)' must be regular.[Regular languages are closed under complementation]

⇒L1' ∩ L2' must be regular.  [De-morgans law]

⇒L2' must be regular. [Regular languages are closed under intersection]

⇒L2 must be regular. [Regular languages are closed under complementation]

But we assumed L2 to be non-regular, Hence proved by contradiction.

Related questions

0 votes
0 votes
0 answers
1
baofbuiafbi asked Nov 14, 2023
152 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.