Ch4 exercises

Ch4 exercises

by Abdelrahman Ashraf Mahmoud Hassan -
Number of replies: 3

In the exercise where

L = { ww' | w, w' ∈ {a,b}*, |w| = |w'| and w ≠ w' },

we are asked to prove that L is not regular.

In the proof, is it sufficient to show that pumping violates only one of the two defining conditions (either |w| = |w'| or w ≠ w'), or do we need to argue that both conditions are violated after pumping?

Since it appears much easier to violate the length condition |w| = |w'| when pumping, is this reasoning correct?



image%20%281%29.png

In reply to Abdelrahman Ashraf Mahmoud Hassan

Re: Ch4 exercises

by Giorgio Satta -

Dear Ashraf, I am not sure I understand completely your question. Let me explain.

In the definition of the language there is only one condition, which is \( w \neq w'\): the part \( |w| = |w'|\) has the only purpose of defining what \( w \) and \( w' \) are, namely the first and the second halves of the string.

If I did not answer to your question, could you please post your approach so that I can better understand your proposal?

In reply to Giorgio Satta

Re: Ch4 exercises

by Abdelrahman Ashraf Mahmoud Hassan -
Dear Professor,

Thank you for the explanation. Let me clarify my confusion more precisely.

My question was not about whether |w| = |w'| is a separate condition, but rather about the choice of proof technique. I was trying to understand why we should not use the pumping lemma here, and instead rely on closure properties, as you mentioned in the lecture.

When I see the language
L = { ww' | w, w' ∈ {a,b}*, |w| = |w'|, w ≠ w' },
it looks structurally similar to classical examples like {a^n b^n}, where pumping the first part breaks the structure and yields a contradiction. For this reason, I was initially tempted to apply the pumping lemma in a similar way.

However, during the lecture you pointed out that in this case the pumping lemma is difficult to apply and that it is preferable to use closure properties instead. My confusion is precisely about why the pumping lemma is not suitable here, even though the language appears to have a global dependency between two parts of the string, as in the a^n b^n example.
In reply to Abdelrahman Ashraf Mahmoud Hassan

Re: Ch4 exercises

by Giorgio Satta -

Dear Ashraf, I think solutions to this problem using the pumping lemma *directly* are possible,  but very difficult for the average ALC student. For instance, strings of the form a^n b^n are in the language, and if you iterate y in the left part for k times you still get a string in the language, so the lemma is satisfied.  

But I need to add that after the lecture,  a couple of students approached me with a p. lemma solution which was correct, although quite involved.