# decidability of regularity of a language depending on representation

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?

• @ Andreas. I didn't want to specify this, as I wanted to know the answer for several different representations, if possible. So let's assume the set is given by a black-box deciding membership (I guess that would mean you have $L$ as an oracle, if you want to check membership with a Turing machine). Also, what if the set was defined by some formula $\varphi$ in some logic (with or without parameters). For example, if $\varphi$ was some expression in first-order logic over $\mathbb{N}$. I know it is a very general question... I'm also happy if I am pointed towards some literature or papers. May 16, 2019 at 13:14
Here is a simple example of a non decidable regular language. Take any language $$L$$ on the alphabet $$A$$. Then the shuffle product $$A^* \mathrel{\raise 1mm{\llcorner\!\llcorner\!\!\!\lrcorner}} L$$ (in other words, the set of all sequences having a subsequence in $$L$$) is always regular, due to Higman's lemma on the subword ordering. Now if $$L$$ is not recursively enumerable, you won't be able to find a finite automaton for $$A^* \mathrel{\raise 1mm{\llcorner\!\llcorner\!\!\!\lrcorner}} L$$.