# Show that language of distinct binary strings is irregular

Let $$Σ =\{\textbf{[},\textbf{]},\textbf{,},\textbf{0},\textbf{1}\}$$, and let $$L⊂Σ^*$$ be the language containing list representations of finite sets of binary strings: i.e., every string $$x∈L$$ is of the form $$x= \textbf{[}x_0\textbf{,} x_1\textbf{,} \ldots\textbf{,} x_n\textbf{]}$$, where:

• for all $$0\le i\le n$$, $$x_i$$ is a string in $$\{\textbf{0},\textbf{1}\}^*$$, and

• none of the $$x_i$$ repeat: if $$i$$ is not equal to $$j$$, then $$x_i$$ is not equal to $$x_j$$.

Show that $$L$$ is not regular.

$$\ \\$$

$$\textbf{EDIT: Below is my attempt: }$$

Suppose $$L$$ is regular.

Suppose the pumping length is n.

Consider the string $$x$$ = $$[0^n, 0^{n-1}, ... , 0]$$.

By the Pumping Lemma, $$x=uvw$$, where

• $$u$$ = $$[$$

• $$v$$ = $$0^n$$, $$0^{n-1}$$, $$0$$

• $$w$$ = $$]$$

Then, $$|v|>0$$ and $$|uv| \leq n$$

So, $$x \in L$$ and $$|x| \geq n$$.

$$\$$

Choose $$k=2$$.

Then, $$uv^2w$$ = $$[0^n, 0^{n-1}, ... , 0 0^n, 0^{n-1}, ... , 0]$$

Since each of the strings in x are repeated, this is a contradiction to the Pumping Lemma. Therefore, $$L$$ is not regular.

• Have you tried using standard techniques, such as the pumping lemma? Dec 4 '19 at 18:41
• @YuvalFilmus I am planning to do it with the pumping lemma, but I'm not sure where to even begin with this question. All I know is that the commas will somehow be repeated and that will somehow lead to a contradiction in the pumping lemma. Dec 4 '19 at 18:42
• @s.67876 You're making a standard PL proof error. Once you pick the string to pump, you aren't allowed to pick particular strings for 𝑢,𝑣,𝑤, instead, you have to derive a contradiction for 𝑎𝑛𝑦 possible choice of those strings. Dec 5 '19 at 14:48

Suppose that the pumping length is $$n$$. Consider the string $$w = [0^n,0^{n-1},\ldots,0].$$ You take it from here.