# How to reduce language is finite to language is regular?

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.

• Show that given a method to test whether a language is regular you can test whether it is finite. – reinierpost Feb 26 '18 at 11:25
• wouldnt that be the opposite direction though ? – zython Feb 26 '18 at 11:28
• 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? – D.W. Feb 26 '18 at 17:35

## 1 Answer

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

• 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. – zython Feb 26 '18 at 11:54
• @PHPNick Assume you know that $M$ defines a regular language, how do you find a finite state automaton that represents its language? – Hendrik Jan Feb 26 '18 at 17:30
• 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. – D.W. Feb 26 '18 at 17:34
• @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. – Hendrik Jan Feb 26 '18 at 23:47