Automata

Question

If $L1$ is regular language and $L2$ is unknown language then what can we say about $L1-L2$. Will it be regular or not?

I think it will be regular because even if $L2$ is not regular then still (Regular - not Regular) will result in Regular, according to the properties of set.

Because subtracting elements that are not elements of a set from The given set will not change the set.

 

I want to know if I am right and if I am not then what's the error?

Answer 1

Let L1 be Σ* , L2 be any language then-

L = L1-L2 = Σ*- L2 = L2' [By definition of complement]

Now it depends on the language L2-

1. If L2 is regular then L2' is regular.

2. If L2 is CFG then L2' may/may not be CFG.

3. If L2 is recursive then L2' is recursive

4. If L2 is R.E then L2' is not necessarily R.E.

Hope you got the point that you cant say what exactly L would behave like.

Comments

Thanks! Your explanation had made it very clear.