regular-languagefinite-automatacomputation-theorypumping-lemma

how do we prove that this language is irregular using the pumping lemma?


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?


Solution

  • Yes, your choice of string is bad for the reason you explain: you cannot know for certain what X is. We can force the choice of X, however. Consider 1 0^p $ 1 0^p. This can only be a string in the language for X = empty and Y = empty. Pumping v can only affect the prefix before $ and will always result in a string not in the language, a contradiction.