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.


This is another classical example in which the pumping lemma is the wrong way to go. Here are two cheap alternatives.

  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.

The trick of using factorials here is standard. Now that you've seen it, you can use it whenever it's needed.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.