I'm trying to reduce $FIN \leq REGU$, where:

$$FIN = \{ \langle M \rangle \vert T(M) < \infty \} \\ REGU = \{\langle M \rangle \vert T(M) \in REG\}$$

Now one thing I have done so far is this:

$ w \in FIN \implies | T(M_w) < \infty \implies \exists n \in N: L(M_w) = \{w_0, \ldots, w_n \} \implies \exists \ \text{DFA} \ A: L(A) = L(M_w) $

What I want to show now that : "to decide if a language is regular is at least as hard as deciding wether it is finite"

Thats where I'm stuck.

I want to remark that this is not homework but, but a exam preparation question.

  • $\begingroup$ Show that given a method to test whether a language is regular you can test whether it is finite. $\endgroup$ – reinierpost Feb 26 '18 at 11:25
  • $\begingroup$ wouldnt that be the opposite direction though ? $\endgroup$ – zython Feb 26 '18 at 11:28
  • $\begingroup$ Please define all notation in your question. What is $T(M)$? What does $T(M) < \infty$ mean? What does $M$ range over? Does $M$ range over Turing machines? $\endgroup$ – D.W. Feb 26 '18 at 17:35

First note, that for a regular language, however encoded, it is decidable wether it is finite or not. So you can use the language $REGU$ as an oracle for $FIN$ in the following way: To check if $\langle M \rangle \in FIN$ you ask the oracle $\langle M \rangle \in REGU$? If the answer is no, you can be sure that $\langle M \rangle \notin FIN$ as every non-regular language is infinite. If the answer is yes there is a proof (e.g. an NFA $\mathcal{A}$) that shows that $M$'s language is regular. Then you run your procedure to check whether $\mathcal{A}$ is finite (this is, as mentioned above decidable).

  • $\begingroup$ ah I think I understand now, you dont go the "undecidablity way" when reducing undecidable problems but actually the other way around. thank you for your answer, I think I understand this better now. $\endgroup$ – zython Feb 26 '18 at 11:54
  • $\begingroup$ @PHPNick Assume you know that $M$ defines a regular language, how do you find a finite state automaton that represents its language? $\endgroup$ – Hendrik Jan Feb 26 '18 at 17:30
  • 1
    $\begingroup$ I don't think this is correct yet. The oracle for $REGU$ just returns yes or no; it doesn't give you a proof, and it doesn't give you a NFA. So this doesn't prove that FIN is decidable, as you haven't shown an algorithm to actually find the NFA in that case. $\endgroup$ – D.W. Feb 26 '18 at 17:34
  • $\begingroup$ @D.W. Exactly. Even for context-free grammars there is no algorithm to construct an equivalent finite state automaton when it is known that the CFG generates a regular language. $\endgroup$ – Hendrik Jan Feb 26 '18 at 23:47

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.