It is well known that many decision problems for regular languages are decidable. However, the proofs seem to rely on a witness of the regularity of said language, be it an automaton, a grammar, a regular expression or whatever.

But what happens if you are presented with a set $L\subset \Sigma^*$ that just happens to be regular. Is its regularity algorithmically decidable? I assume it is, if I have a defining formula $\varphi$ of some simple enough sort. But is there a crisp boundary as to what kind of representation is necessary?

Thanks for reading!

1more comment