prove that language $Y$ is not regular

Question

$\sum=\{1, \#\}$
$Y=\{w| w=x_1\#x_2\#...\#x_k\ \ k\ge 0\ \ \ x_i\neq x_j\ \text{for}\ i\neq j \}$ Prove that language $Y$ isn't regular.

I know pumpping lemma. Firstlty I don't understand this language ? What does mean $k$ ? Is it fixed ? Any example, please ?

Answer 1

$Y$ is the set of all words of the form

$$1^{n_1}\#1^{n_2}\#\ldots\#1^{n_k}\tag{1}$$

such that the numbers $n_1,n_2,\ldots,n_k$ are all different, and $k\ge 0$. Two values of $k$ are perhaps a little tricky. When $k=1$, $(1)$ becomes simply $1^{n_1}$, a string of $n_1$ ones; there are no $\#$s. And when $k=0$, $(1)$ is simply the empty string, which you probably denote by either $\epsilon$ or $\lambda$.

In other words, $Y$ is the set of all strings consisting of blocks of ones such that

• no two blocks of ones are the same length,
• adjacent blocks are separated by a single $\#$, and
• the empty string of zero blocks is allowed.

You want to use the pumping lemma to show that $Y$ is not regular. I’ll get you started with a word to which you can usefully apply the pumping lemma.. Assume that $Y$ is regular, let $p$ be the pumping length, and let

$$s=1^p\#1^{p+1}\#1^{p+2}\#\ldots\#1^{2p}\;.$$

If you need more help after thinking about it for a while, you’ll find a further hint in the spoiler-protected block below.

Apply the pumping lemma to decompose $s$ in the form $xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in Y$ for each $k\ge 0$. Get a contradiction when $k=2$.