# Pumping lemma of regular language [duplicate]

I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \{1,\#\}$, consider

$$D=\{w \mid w=x_1 \# x_2 \# \cdots \# x_k \text{ for } k \geq 0, \text{ each } x_i \in 1^*, \text{ and } x_i \neq x_j \text{ for } i \neq j\}.$$

I want to know how to prove this is not regular using pumping lemma.

## marked as duplicate by David Richerby, Raphael♦Feb 25 '15 at 15:15

1. Use the Myhill–Nerode theorem. For any $i \neq j$, the words $1^i$ and $1^j$ are inequivalent, since $1^i\#1^i \notin D$ while $1^i\#1^j \in D$. Since there is an infinite pairwise inequivalent collection of words, the language is not regular.
2. Use closure operators. If $D$ were regular, then so would $\overline{D} \cap 1^*\#1^* = \{1^i \# 1^i\}$ be. Now it's easy to use the pumping lemma.
It's also possible to use the pumping lemma directly. Suppose that the pumping length is $p$. Take $w = 1^p\#1^{p!+p} \in D$. According to the pumping lemma, we can write $w = xyz$ so that $0 < |xy| \leq p$ and $xy^iz \in D$ for all $i$. Let $y = 1^q$, so that $1 \leq q \leq p$. Choose $i = p!/q + 1$. Then $xy^iz = 1^{p!+p} \# 1^{p!+p} \notin D$, contradiction.