1
$\begingroup$

Is the language $L = \{ w \mid w $ is $ 3^n - 1 $ in some given representation $, n > 0 \}$ regular? I know that it is regular. If each element in $L$ is represented as decimal numbers, $L = \{ 2, 8, 26, 80, 242, \ldots \}$. If in binary, $L = \{ 10, 1000, 11010, 1010000, 11110010, \ldots \}$. However, if in ternary, $L = \{ 2, 22, 222, 2222, 22222, \ldots \}$. From there, it is clear that a DFA can be designed to show that $L$ is regular. But what if it wasn't ternary that it became clear, but instead base 59 or base 1009?

My question is that for other sets, does there exist a clear method to determine if the language based on that set is regular or not? Or does it just depend on the cleverness of the solver?

$\endgroup$
  • $\begingroup$ When we talk about a language being regular, we're talking about some subset of strings over a language. As far as I know, there's no real way to extend this naturally to numbers and they're associated operations,so the regularity of your language will depend on how you choose to covert numbers to strings as you have done. $\endgroup$ – user979616 Mar 18 '16 at 6:15
  • $\begingroup$ Yes, that is a good point. Usually, the language will be a set of strings over some alphabet, be it binary, ternary, etc. I guess what I am trying to ask is if we can determine whether or not there exists some alphabet where the set represented as a language over that alphabet is regular. $\endgroup$ – miles Mar 18 '16 at 8:14
  • $\begingroup$ If I read that definition of $L$, I'll understand the language to be $\{3\}^*$. Anyway, I think our reference questions have answers for you. $\endgroup$ – Raphael Mar 18 '16 at 8:19
  • $\begingroup$ Yes, after reading a bit, it seems my amateur study has not taught me to write proper notation for languages. The original question is incomplete and there are infinite answers since there are infinite bases to use as the alphabet. $\endgroup$ – miles Mar 18 '16 at 8:35
  • $\begingroup$ Your question seems to be very close to this one DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$. $\endgroup$ – J.-E. Pin Mar 30 '16 at 17:50
4
$\begingroup$

See DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$.

The proof for $L'=\{w \mid w \in \{0,1\}^*, w $ is $3^n$ in binary for some $ n > 0 \}$ is not regular can be easily modified to prove that $L'=\{w \mid w \in \{0,1\}^*, w $ is $3^n - 1$ in binary for some $ n > 0\}$ is not regular.

However in ternary the same language is regular. It is similar to case of $2^n$ and $2^n-1$. So for some bases you might be able to prove these kind of languages regular but for others you may not.

$\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.