1
$\begingroup$

I'm attempting to figure out if a union of two languages is regular.

$$ L_1 = \{all\ the\ words\ in\ the\ Oxford\ dictionary\} \\ L_2 = \{w : w\ has\ twice\ as\ many\ a's\ as\ b's\} $$

$L_2$ is well established to be a non-regular language. However, I am not sure if $L_1$ would be considered a regular language. The language should be finite (albeit large), which suggests it is regular, but I'm not certain.

If $L_1$ is regular, then I would consider the union $L_1 \cup L_2 $ would also be regular, as by the same argument, the language would be finite.

What does everyone think?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ L1 union L2 is not regular as the previous answer suggests but L1 intersection L2 is definitely regular. As their intersection will contain only the common elements of both the sets, which will finite and also regular. $\endgroup$ – Bharat Banavalikar Feb 27 '16 at 20:21
  • 1
    $\begingroup$ You seem to have serious issues with the definition of union of languages. The union of a finite and an infinite set is always infinite. Unless you mean intersection, but that is a very different question. $\endgroup$ – vonbrand Feb 28 '16 at 2:57
2
$\begingroup$

The best way to see that $L_1 \cup L_2$ is not regular is through closure properties of the regular languages.

Theorem. If $L_1$ is finite and $L_2$ is not regular, then $L_1 \cup L_2$ is not regular.

Proof. Since $L_1 \setminus L_2$ is finite, it is regular. Suppose $L = L_1 \cup L_2$ were regular. Then $L \setminus (L_1 \setminus L_2) = L_2$ would also be regular, contrary to assumption. $\qquad\square$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$L_1$ is indeed finite. But the union $L_1\cup L_2$ contains everything that is in $L_1$ and also everything that is in $L_2$. Thus, the union of a finite set and an infinite set is infinite.

In this case, $L_1\cup L_2$ is not regular: you can prove this using the pumping lemma, Myhill–Nerode or any other technique you might have been taught.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ More generally, I think the union of any irregular/non-context-free/non-context-sensitive language and a finite language is irregular/non-context-free/non-context-sensitive. $\endgroup$ – G. Bach Feb 27 '16 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.