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 '19 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 '19 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 '19 at 13:14
  • $\begingroup$ @Benjamin. Thanks, is that obvious or can you point to some literature? $\endgroup$ – Sebastian Mueller May 16 '19 at 13:19
  • 1
    $\begingroup$ Rice’s theorem covers the Turing machine. $\endgroup$ – Benjamin Steinberg May 16 '19 at 14:04

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


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.