0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$

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