1
$\begingroup$

To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc.

Given the set $S$ of natural numbers such that $S = \{2^i| i \in \mathbb{N}\}$ prove that for some base representation of set $S$, the resulting language is not regular.

I have tried but I can't seem to figure out how to prove this. I figure that base 3 would probably result in a nonregular language, but then how would I prove it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You are right in saying that the binary representation of the language is regular because it is defined by the expression $10^*$(regular expression). You are also right in saying that this does not hold for the ternary representation. You can prove the latter in various ways including the "calssic" pumping lemma (quite cumbersome in this case) or using Cobham's Theorem.

This theorem says that if you have a subset of $\mathbb{N}$ and you take $m,n \in \mathbb{N} $ such that they are multiplicatively independent, then your set is recognizable by finite automata in both $m$-ary and $n$-ary notation if and only if it is ultimately periodic.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the clarification! I wanted to try and prove this with the pumping lemma, can you give ma hint as to how I should do this? $\endgroup$
    – Noobcoder
    Commented Dec 4, 2019 at 14:34

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.