while solving, I came across a tricky question that asked me to prove that a certain language is irregular using the pumping lemma. that question is as follows:
prove that the language L is irregular using the pumping lemma, where L is a language over the alphabet {0,1,$}.
L = { XW$WY | X,Y ∈ {0,1}*, W ∈ {0,1}+ }
my approach was to pick a string the string S = 0p$0p where X and Y are equal to Э, and P is the pumping length.
Now, let's divide the string into 3 parts let's call them Y1,Y2,Y3.
to fulfill the conditions of the pumping lemma, the concatenation of the 3 parts would have to have a length > P, and |Y2| > 0, and |Y1Y2| <= P.
so our Y1 and Y2 would consist of 0s only, and Y3 would be $0p. so, our string would look like this: 0i0j$0p where i+j <= P. clearly pumping Y2(0j) would change the length of first W so the new string Y1Y2iY3 would not belong to L. but what's confusing me is the fact that we can always change X to make the first W equal to the second. so, whatever the i is, we can always assume that the difference in length is actually because of X. am I missing something?
