1
$\begingroup$

Consider the language $$ L = \{2^k : k \text{ is prime}\}. $$ This language contains, for example, $2^3=222$, $2^5=22222$, $2^7=2222222$, and so on.

I know that $L$ is irregular and so there must exist a set of strings that are pairwise distinguishable with respect to $L$, but I'm struggling to come up with such a set of strings. Any help would be appreciated!

$\endgroup$
1
  • $\begingroup$ Maybe I didn't understand something, but $\Sigma^*$ is regular, but still follows your definition. $\endgroup$
    – nir shahar
    Sep 29 at 4:51
0
$\begingroup$

You can choose $2^*$ as your set of words. Indeed, consider the words $2^a,2^b$, where $a < b$. If these words are indistinguishable then for all $c \geq 0$, $a + c$ is prime iff $b + c$ is prime. Since there are infinitely many primes, we can find a prime $p \geq a$. Let $c_1 = p-a$. Since $p$ is prime, so is $b + c_1 = p + (b-a)$. Choosing $c_2 = p-a+(b-a)$, we similarly get that $b + c_2 = p + 2(b-a)$ is prime. Continuing in this fashion, we see that $p + k(b-a)$ is prime for all $k \geq 0$. In particular, $p + p(b-a)$ should be prime. But $p + p(b-a) = p(b-a+1)$ clearly isn't prime. This contradiction shows that $2^a,2^b$ are distinguishable.

$\endgroup$
0
$\begingroup$

Take the sets 2^p where p is prime and the gap between p and the next larger prime is some number g fixed for that set. Sets with different g can be distinguished, and gaps between consecutive primes become arbitrary large.

This applies when you don’t take primes, but numbers f(n) where f(n) / n goes towards infinity. Trivial cases would be squares, cubes, factorials etc. instead of primes. Or any subsets of these.

$\endgroup$

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.