# Set-theoretic difference of two languages in CFL - REG

Let $$L_1,L_2\in$$ CFL $$-$$ REG, with $$L_1\subset L_2$$. Which of the following always holds?

1. $$L_1-L_2\in$$ CFL $$-$$ REG and $$L_1-L_2\in$$ REG.
2. $$L_1-L_2\in$$ REG and $$L_2-L_1\in$$ CFL $$-$$ REG.
3. $$L_1-L_2\in$$ REG. $$L_2-L_1\in$$ REG.
4. $$L_1-L_2\in$$ REG. As to $$L_2-L_1$$, it may be in REG or not.
5. None of the above.
• What do you think? – Yuval Filmus Feb 11 at 15:24
• First statement states that L1, L2 are context free languages which are not regular and L1 is a subset (a part) of L2. L1 - L2 will then be null. L2 - L1 will be those strings which are in L2 but not in L1. Answer according to me should be (b) – kiner_shah Feb 11 at 15:35
• I thought it might be non of the above – Yair Ayalon Feb 11 at 17:37
• @kiner_shah I understand what you're saying and it seems reasonable – Yair Ayalon Feb 11 at 17:38
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX). Don't forget to give proper attribution to your sources! – D.W. Feb 11 at 20:54

Since $$L_1-L_2=\emptyset\in$$ REG, we only need to consider $$L_2-L_1$$.
Consider $$L_1=\{a^nb^n\mid n\text{ is a positive integer}\}, L_2=\{a^nb^n\mid n\text{ is a non-negative integer}\}$$, then $$L_2-L_1=\{\epsilon\}\in$$ REG.
Consider $$L_1=\{a^nb^n\mid n\text{ is a positive odd integer}\}, L_2=\{a^nb^n\mid n\text{ is a positive integer}\}$$, then $$L_2-L_1=\{a^nb^n\mid n\text{ is a positive even integer}\}\in$$ CFL $$-$$ REG.