4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is your question? Please state precisely exactly what you are trying to prove. Right now we're forced to guess what is the precise statement you are trying to prove. Also, what's the context where you encountered this? Can you credit the original source of this exercise? $\endgroup$ – D.W. Aug 9 '18 at 1:44
  • $\begingroup$ I’m trying to prove that the symmetric difference (defined as: (L1-L2)U(L2-L1)) between L a context free language and F a finite language will always yield a non-regular language. $\endgroup$ – Euclid Aug 9 '18 at 1:47
  • $\begingroup$ Automata and Formal languages. $\endgroup$ – Euclid Aug 9 '18 at 1:48
  • $\begingroup$ Symmetric difference is similar to XOR (all the words that are in one and only one of the two languages) $\endgroup$ – Euclid Aug 9 '18 at 1:49
  • $\begingroup$ @D.W. Forgot to reply $\endgroup$ – Euclid Aug 9 '18 at 1:53
2
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.