Question

The following language over Σ = {1, #} contains #-separated lists of distinct unary values: A = {x1#x2# . . . #xk | k ≥ 0, xi = 1∗ for all i = 1 . . . k, xi 6= xj for all i 6= j} Use the pumping lemma to show A is not regular. In other words, give a string s ∈ A and argue that no matter how you partition s = xyz with |y| > 0, |xy| ≤ p, there exists some i = 0, 2, 3, . . . such that xyi z 6∈ A.

Answer 1

Let the language A be assumed to be regular. Then according to the pumping lemma A must have a pumping length. Let p be the pumping length.

Now, let the string be considered, where is x times 1.This string must belong to A since it agrees to the definition of A.
According to the pumping lemma, the string can be partitioned into such that , and .
Suppose does not contain any and is only made of 's. Then, if the string is considered, it excludes some 's from the segment containing . That would decrease the number of 's in that segment. But on decreasing the number of 's, it will result in a segment which is equal in length to some other segment to the left, as segments of all lengths less than it are present in the string. Thus, .
If there are more than one in , then the string will have at least two segments having equal number of 's. This violates the definition of A and hence .
So, must have one . But in that case, if is pumped multiple times then there will be segments of equal length.

Thus the pumping lemma is violated for A and so A cannot be regular.