1
$\begingroup$

I'm trying to prove $\mathsf{FIN} \leq_T \mathsf{REGU}$, where

$$\mathsf{FIN} = \{ \langle M \rangle \mid M\text{ is a Turing machine}, L(M) \text{ is a finite language}\},$$ $$\mathsf{REGU} = \{\langle M \rangle \mid M\text{ is a Turing machine}, L(M) \text{ is a regular language}\},$$ $\langle M\rangle$ is the encoding of $M$, $\,$$L(M)$ is the language accepted by $M$ and $\leq_T$ means Turing reduction.

What I have done so far is this:

$ w \in \mathsf{FIN}$ $\implies$ $| L(M_w)| < \infty$ $\implies$ $\exists n \in \mathbb 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: "to decide if a language is regular is at least as hard as deciding wether it is finite". That's where I'm stuck.

$\endgroup$
4
  • $\begingroup$ Show that given a method to test whether a language is regular you can test whether it is finite. $\endgroup$ Feb 26, 2018 at 11:25
  • 1
    $\begingroup$ wouldnt that be the opposite direction though ? $\endgroup$
    – zython
    Feb 26, 2018 at 11:28
  • $\begingroup$ @zython, will you be interested if I write a correct answer? The accepted answer is not correct. $\endgroup$
    – John L.
    Feb 24, 2022 at 1:26
  • $\begingroup$ @JohnL. yes, please; if its no big effort for you. however its been a while since I have had to deal with formal lanuages so I myself might not be able to differentiate a correct from an incorrect answer anymore. $\endgroup$
    – zython
    Feb 24, 2022 at 12:37

2 Answers 2

1
$\begingroup$

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

$\endgroup$
4
  • $\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, 2018 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$ Feb 26, 2018 at 17:30
  • 2
    $\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, 2018 at 17:34
  • 1
    $\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$ Feb 26, 2018 at 23:47
1
$\begingroup$

The simple obvious approach

To prove $\mathsf{FIN} \leq_T \mathsf{REGU}$, what we can do is to find a "computable" mapping that maps

  • any finite language to a regular language and
  • any infinite language to a nonregular language.

The wanted mapping

If words in a regular language are ordered by length, the differences between lengths of adjacent words are bounded. In fact, we can see immediately that they are bounded by the pumping length of that language as in the pumping lemma for regular languages.

The idea to design the mapping is, when the words in the given language become longer, we will ensure the differences between different lengths of the corresponding words become bigger so that they cannot be bounded eventually.

Given a language $L$, we can map it to $$f(L)=\{w\in \Sigma^*\mid w \text{ has a prefix }u\in L\text{ such that } |w|=|u| + |u|^2 \}$$ where $|\cdot|$ is the length of a string. Let us prove $f$ can be the wanted mapping.

Claim. $L$ is finite $\iff$ $f(L)$ is regular.

Proof. "$\implies$": If $L$ is finite, then $f(L)$ is finite as well. Hence $f(L)$ is regular.

"$\impliedby$": This is an application of the pumping lemma. Suppose $f(L)$ is regular. Let $p$ be a pumping length for $f(L)$. For the sake of contradiction, assume $L$ is not finite. Then there must be a word $u\in L$ with $|u|\ge p$.

Consider $w=uu^{|u|}\in f(L)$. Since $|w|\ge p$, the pumping lemma says $w=xyz$ for some strings $x,y,z$ such that $1\le|y|\le p$ and $xy^2z\in f(L)$. Since $$|xy^2z|=|y| + |w| = |y| + (|u| + |u|^2),$$ we know $$|u| + |u|^2<|xy^2z|<(|u|+1) + (|u|+1)^2.$$ Since the length of every word in $f(L)$ is of the form $i + i^2$ for some natural number $i$, we must have $xy^2z\not\in f(L)$, which contradicts the fact $xy^2z\in f(L)$. $\quad\checkmark$

From Turing machine $M$ to $M'$

Given a Turing machine $M$, let us construct Turing machine $M'$.

On input string $w$, $M'$ will try searching a prefix $u$ of $w$ such that $|w|=|u| + |u|^2$. This can be done by letting $u$ loop through each prefix of $w$, or just checking whether $|w|=\lfloor\sqrt{|w|}\rfloor+\lfloor\sqrt{|w|}\rfloor^2$.

  • If there is no such prefix, $M'$ rejects.
  • Otherwise, $M'$ has found $u$ as such. $M'$ will continue to run in the same way as $M$ runs given $u$ as the input.

It is clear that we can construct $M'$ from $M$ algorithmically. A word $w$ is accepted by $M'$ if and only if $w$ has a prefix $u$ such that $\vert w\vert=\vert u\vert+\vert u\vert^2$ and $M$ accepts $u$. That is, $L(M') = f(L(M))$. thanks to the claim above, we know $\langle M\rangle\in\mathsf{FIN}$ $\iff$ $\langle M'\rangle\in\mathsf{REGU}$.

A Turing reduction from $\mathsf{FIN}$ to $\mathsf{REGU}$

Given a string $s$, here is how we decide whether $s\in \mathsf{FIN}$ using an oracle that tells whether any given string is in $\mathsf{REGU}$, .

  1. Check whether $s$ is a valid encoding of a Turing machine. If not, $s\not\in \mathsf{FIN}$.
  2. Otherwise, $s=\langle M\rangle$ for some Turing machine $M$. Construct $M'$ from $M$ as described above. So, $\langle M\rangle\in\mathsf{FIN}$ $\iff$ $\langle M'\rangle\in\mathsf{REGU}$. Now ask the oracle whether $\langle M'\rangle\in\mathsf{REGU}$.
    • If yes, $s\in\mathsf{FIN}$.
    • If not, $s\not\in\mathsf{FIN}$. $\quad\checkmark$

An exercise.

Show that $\mathsf{REGU} \leq_T \mathsf{CF}$, where $$\mathsf{CF} = \{\langle M \rangle \mid M\text{ is a Turing machine, }L(M)\text{ is a context-free language}\}.$$

The simple obvious approach is, similarly, to find a "computable" mapping that maps any regular to a context-free language and any non-regular language to a non-context-free language. If such a mapping is known to you, this exercise is easy; otherwise, it is pretty hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.