If $L_1 \cup L_2$ is regular and $L_1$ is a finite language, then $L_2$ is regular

775 Views Asked by At

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression.

So, Assume that we have a regular language like $L=L_1 \cup L_2$ and we know that $L_1$ is a finite language. How can we prove that $L_2$ is regular too?

Note: My idea to prove this is that every finite language is a regular language. So, $L_2$ should be regular too. Is this true ? If so, are there better proofs for this?

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, every finite language is regular, so $L_1$ is regular, not $L_2$. You haven't shown how to conclude that $L_1$ is regular from this.

Instead, let $L_3 = L_1 \setminus L_2$ be the set of words which are in $L_1$ but not $L_2$. Since $L_1$ is finite, so is its subset $L_3$. A finite language is regular, so $L_3$ is regular, and thus its complement $\bar{L}_3$ is regular too. Finally, $$L_2 = (L_1 \cup L_2) \cap \bar{L}_3$$ is the intersection of two regular languages, hence it is regular.