1
$\begingroup$

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!

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

1 Answer 1

1
$\begingroup$

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

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