Difference between a regular and a non-regular language

Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then: is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM? is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?

954 1 1 gold badge 5 5 silver badges 17 17 bronze badges asked Dec 5, 2020 at 20:57 user129239 user129239 45 2 2 bronze badges

3 Answers 3

$\begingroup$

First, we know that, $L$ is a regular language if and only if its complement be regular language.

On the other hand, $$L_1\setminus L_2=L_1\cap L_2^c.$$

Suppose $\Sigma=\$ , Let $L_1=\Sigma^*$ , and $L_2=\Sigma^*\setminus \$ , obviously, $L_2$ isn't regular, so

$$L_1\setminus L_2=\ $$ consequently, $L_1\setminus L_2$ can be a non-regular.

Let $L_1=\emptyset$ , and $L_2$ be any non-regular language, so

consequently, $L_1\setminus L_2$ can be regular.

for the second proposition, let $L_1=\emptyset$ , and $L_2$ be a non-regular language, so $L_2\setminus L_1$ is non-regular, and if we set $L_1=\Sigma^*$ , and $L_2$ be a non-regular language, then $L_2\setminus L_1=\emptyset$ that show us $L_2\setminus L_1$ can be regular.

Note that, difference between two non-regular, regular languages can be regular or not.