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$ – Yuval Filmus Dec 4 '19 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 '19 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$ – Rick Decker 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.

| cite | improve this answer | |
  • $\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 '19 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 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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