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.

  • 1
    $\begingroup$ Have you tried using standard techniques, such as the pumping lemma? $\endgroup$ Dec 4, 2019 at 18:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – s.67876
    Dec 4, 2019 at 18:42
  • $\begingroup$ @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. $\endgroup$ Dec 5, 2019 at 14:48

1 Answer 1


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

  • $\begingroup$ I did an attempt using this starting point. I know my formatting is a bit off, I'm still new to this. But does the proof make sense? $\endgroup$
    – s.67876
    Dec 4, 2019 at 19:16
  • $\begingroup$ Using @YuvalFilmus' hint, your pumped string has to be all zeros, if you leave it out, the result repeats. $\endgroup$
    – vonbrand
    Feb 10, 2020 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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