1
$\begingroup$

$ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $ Proof or disproof Fin = Fin-Complete Where Fin-Complete means that for every $ L_1,L_2 \in Fin $ there exist a valid reduction $ L_1 \leq L_2 $

my trial:

Consider two languages $ L_1 $ and $ L_2 $ where $ L_1 $ contains a single string s $ L_1 = \{ s \} \ s \in \Sigma^* $ and $ s \neq \epsilon $ a finite language of size 1. Let $ L_2 = \emptyset $ the empty language, which is also finite by definition as it contains zero strings. By the definition of reduction, $ L_1 \leq L_2 $ there must exist a computable function $ f $ such that for any string $ w \in L_1 $ if and only if $f(w) \in L_2 $ however since $ L_2 = \emptyset $ there are no strings in $ L_2 $ for $ f(x) $ to map to construct such a function f that satisfies the condition for all $ w\in L_1 $

$\endgroup$
2
  • 1
    $\begingroup$ By your definition Fin does not contain the empty set: $|L| > 0$. $\endgroup$ Feb 2 at 10:20
  • $\begingroup$ right i miss that thank u $\endgroup$
    – maya cohen
    Feb 2 at 10:58

1 Answer 1

2
$\begingroup$

The claim is correct. To see why, note that every language in $L\in Fin$ is non-trivial and regular. Indeed, $L$ is not empty, by the definition of $Fin$, and does not equal $\Sigma^*$ as then it would be infinite. Now the claim follows from the fact that every regular language is decidable, and the fact that every non-trivial language is $R$-hard. Specifically, for every two languages $L_1, L_2 \in Fin$, we have that $L_1 \in \text{REG} \subseteq \text{R}$ and $L_2 \notin \{ \emptyset, \Sigma^*\}$. Hence, we conclude that $L_1\leq_m L_2$.

$\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.