Ch4 exercises

Ch4 exercises

by ABDELRAHMAN ASHRAF MAHMOUD HASSAN -
Number of replies: 1

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?