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!

  • 3
    $\begingroup$ If you give a language by a Turing machine you cannot decide if it is regular, so these things of course depend on the representation. I would guess you would need to be more specific about what sorts of representations you allow in order to get a precise answer. $\endgroup$ – Benjamin Steinberg May 16 at 12:58
  • 2
    $\begingroup$ What do you mean by "presented with a set"? Are you just given a black box for deciding membership in the set? Or an algorithm fo deciding membership? Or an algorithm that lists the members of the set? Or what? $\endgroup$ – Andreas Blass May 16 at 13:01
  • $\begingroup$ @ 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. $\endgroup$ – Sebastian Mueller May 16 at 13:14
  • $\begingroup$ @Benjamin. Thanks, is that obvious or can you point to some literature? $\endgroup$ – Sebastian Mueller May 16 at 13:19
  • 1
    $\begingroup$ Rice’s theorem covers the Turing machine. $\endgroup$ – Benjamin Steinberg May 16 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.