1
$\begingroup$

Choose some set in the natural numbers such that the language formed by the set under binary representation is a regular language, but is not regular under any other language formed by some base. Prove this using the pumping lemma.

I chose the set $S = \{2^i|i\in\mathbb{N}\}$. It is quite easy to prove this is a regular language under binary representation, but how would you prove that this is not regular under some other base (ie. ternary, quaternary, etc.) using the pumping lemma?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The pumping lemma is used to prove a language is not regular, while you want to prove the language is regular. $\endgroup$
    – integrator
    Commented Dec 3, 2019 at 21:48
  • $\begingroup$ Are there no restrictions at all on $S$ aside from being some subset of $\mathbb{N}$? $\endgroup$
    – mhum
    Commented Dec 3, 2019 at 22:00
  • $\begingroup$ I think I misinterpreted the question, after reading it again I have found that it is asking to choose some set S such that there is some base n for which the representation of S is regular and another base for which S representation is not regular. And we must prove it. $\endgroup$
    – Noobcoder
    Commented Dec 3, 2019 at 22:35
  • $\begingroup$ Given the misinterpretation, it would be a good idea (for archival reasons at least) to edit your question to reflect the intended changes. $\endgroup$
    – Rick Decker
    Commented Dec 4, 2019 at 15:26
  • 1
    $\begingroup$ Answered on cstheory: cstheory.stackexchange.com/questions/2083/…. $\endgroup$
    – Yuval Filmus
    Commented Dec 4, 2019 at 18:39

0

Reset to default

Browse other questions tagged or ask your own question.