Given an arbitrary language L is there an algorithm that terminates and decides whether the language is regular or not?

85 Views Asked by At

I have an arbitrary language $L$ (with finite amount of symbols $k$), assume the language can be represented in finite space as an input, you can also assume that we can check for $w\in\Sigma^*$ whether $w\in L$ (in finite time)

I have the following algorithm

n=1;
while(true){
  calculate_enumeration_of_all_n_DFA(n) enum; 
  forall(a in enum){
    if (L(a)=L) 
    return a
  }; 
n=n+1
};

The algorithm may not terminate but if it does we have proved that $L$ is regular

Is there an algorithm that decided whether $L$ is regular and terminates?

And if not, is it because we have not found one yet - or is it because there cannot exist one?