0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you :) Great proof ! $\endgroup$ Commented Apr 3, 2016 at 15:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .