The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$.
Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric difference yields a non regular language.
Although this looks like it should be a very simple problem and it seems very obvious to me since I’m only changing the language finitely, I can’t seem to prove it.
My progress:
we have: (L-F)U(F-L). the right hand side is a finite language. So this problem will be solved if we prove these two statements: A) L-F is non regular when L and F are non regular and finite (respectively). B) LUF is non regular when L and F are non regular and finite (respectively).
I originally thought I had a very simple solution for each of these using a proof by contradiction with the pumping lemma (based on the largest length of a word in the finite language) but I later remembered that the pl is not a sufficient condition to be regular thereby invalidating my argument.
Something that seemed like a good approach is the Myhill-Nerode theorem but I can’t seem to get anywhere because I wasn’t able to prove that there must be an infinite number of “dividing words” z which would mean the finiteness of F could not account for them.
In the end I came up with a simple proof by contradiction of A using regular expressions, But can’t seem to get B using a similar approach.
So, if you can help me solve B or the original problem that would be great.
