Question

Prove whether the following are regular (include regular expression) or not regular (show proof). The alphabet is {0, 1}

Given L1 and L2 are regular, L3 = {all stings in L1, but not in L2} Is L3 regular?

I'm not sure what theorems i can use to prove this. I appreciate anything you can provide.

Answer 1

Given that L1 and L2 are regular language.

Now L3 contain all strings in L1 but not in L2.

L3 can be written as L3 = all strings of L1 but that string must not be in L2

So, L3 = L1 - L2

Using demorgan's law L1 - L2 = L1 (L2)'

Now, according to closure property of regular language if L is regular language then L' (compliment of L) is also regular because we can make a DFA for L' using L by exchanging final and non-final states.

So, since L2 is regular (L2)' is also regular as well.

From the closure property of regular language we know that intersection of two regular language always results a language which is also regular .

Since, L1 and (L2)' are regular language their intersection will also be a regular language because we can make a DFA for that resultant language.

So, L3 which is obtained after intersection of two regular languages L1 and (L2)' is also a regular language.

Therefore, L3 is regular language

Hence, proved