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!

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .