How do I prove that this language is not regular?

Question

I'm doing the practice questions in my text book so I can gain some experience, but this question keeps getting the better of me.

Let $\Sigma = \{1 , \#\}$ and let $Y=\{w \mid w = x_1\#x_2\#...\#x_k, k \ge 0, x_i ∈ 1^* , i \neq j \rightarrow x_i \neq x_j \}$. Prove that Y is not regular. Can you please help?

Answer 1

Hint: Use the Pumping Lemma for regular languages. Assume that $Y$ is regular and has pumping constant $p$. We must then have that whenever $s \in Y$ and $|s| \geq p$, we can write $s = xyz$ for some strings $x$, $y$ and $z$ such that

1. $|xy| \leq p$
2. $|y| > 0$
3. $xy^iz \in Y$ for all $i \geq 0$

Now consider the string $s$ given by

$$1^p \# 1^{p-1} \# 1^{p-2} \ldots 1^2 \# 1$$

Clearly, $s \in Y$. Where should $y$ be? Can condition 3 hold for all $i \geq 0$?

Answer 2

We can use the Pumping lemma for Regular Languages:

Assume Y is regular and let p be its pumping length. Choose s to be $1^p$#$1^{p−1}$#$1^{p−2}$…#$1^2$#$1$

Then s is clearly in the language, and |s|$\ge$ p. Now, if we decompose s into xyz where the conditions of the PL hold, we can have:

x = $1^{p-1}$, y = $1$, z = #$1^{p−1}$#$1^{p−2}$…#$1^2$#$1$ (the rest of s)

Then |xy| $\le$ p, |y| $\gt$ 0, but x$y^0$z is not in Y, since this yields the string

$1^{p-1}$#$1^{p−1}$#$1^{p−2}$…#$1^2$#$1$, which doesnt satisfy the second condition for Y.

Since the third condition of the PL fails for i=0, the language Y is not regular.

Answer 3

Hint. Suppose your language $Y$ is regular. Then the language $X = 1^*\#1^* - Y$ would be regular. But $X = \{1^n\#1^n \mid n \geqslant 0 \}$. Can you prove now that $X$ is not regular to conclude the proof?