0
$\begingroup$

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?

$\endgroup$
1
$\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=\{a,b\}$, Let $L_1=\Sigma^*$ , and $L_2=\Sigma^*\setminus \{a^nb^n\}$, obviously, $L_2$ isn't regular, so

$$L_1\setminus L_2=\{a^nb^n\} $$ consequently, $L_1\setminus L_2$ can be a non-regular.

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

$$L_1\setminus L_2=\emptyset$$

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.

$\endgroup$
0
$\begingroup$

Be $\Sigma$ an alphabet, consider $L_1=\Sigma^*$ and $L_2$ a non-regular language, then also its complement, i.e. $L_1\setminus L_2$, is non-regular (remember that the family of regular language is closed under complement). On the other hand, if $L_1=\varnothing$ (which is regular), then $L_1\setminus L_2$ is regular even if $L_2$ is not.

For $L_2\setminus L_1$, first consider $L_1=\Sigma^*$ and $L_2$ any (non-regular) language, then $L_2\setminus L_1$ is regular. On the other hand, if $L_1=\varnothing$ and $L_2$ is a non-regular language, then $L_2\setminus L_1$ is non-regular.

$\endgroup$
-1
$\begingroup$

$L_1 - L_2$ and $L_2 - L_1$ are both non regular since $L_2$ cannot be decided by finite automata. Intuitively, to know whether a string is in $L_2$ or not, we need something more powerful than a finite automata.

$\endgroup$

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.