A binary string $a$ (of length $n\geq0$) is a finite sequence $(a_1,\ldots,a_n)$, with $a_i\in\{0,1\}$. We write this as $a=a_1\cdots a_n$. If the length is zero we write the binary string as $\varepsilon$. The concatenation of two binary strings $a=a_1\cdots a_n$ and $b=b_1\cdots b_m$ is defined to be $ab=a_1\cdots a_n\cdot b_1\cdots b_m$.

A binary string $a$ is said to be a substring of $b$, if there exist binary strings $x,y$ such that $b=xay$. We say $a$ is a proper substring of $b$ if $a\neq b$ and $a$ is a substring of $b$.

Does there exist an infinite set $S$ of binary strings such that for all $a,b\in S$, $a$ is not a proper substring of $b$?

  • $\begingroup$ what have you looked at so far ? $\endgroup$ – user451844 Jul 7 '17 at 2:22

$101,1001,10001,100001, \dots$


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.