patternMinor
Is the symmetric difference of a non regular language L and a finite language f non regular?
Viewed 0 times
symmetricthefinitenonregularlanguagedifferenceand
Problem
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.
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.
Solution
Denoting symmetric difference by $\Delta$, note that $(L \Delta f) \Delta f = L$. This suggests the following strategy: show that the symmetric difference of a regular language and a finite language is regular. This implies your claim via proof by contradiction.
The product construction shows the stronger fact that the symmetric difference of two regular languages is regular. Hence you can strengthen your claim by replacing "finite" with "regular".
The product construction shows the stronger fact that the symmetric difference of two regular languages is regular. Hence you can strengthen your claim by replacing "finite" with "regular".
Context
StackExchange Computer Science Q#96094, answer score: 4
Revisions (0)
No revisions yet.