Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable.

This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ then we can have a solution of $A$ as well. Hence $A$ is decidable.

We know that regular languages is always decidable.

Corollary:2 So from (Corollary:1)if $A\leq_m^\mathsf{}B$ and $B$ is regular then $A$ is should also be regular.

But I have made this wrong my taking Counterexample. For example, define the languages $A = \{ 0^n1^n \mid n\ge 0 \} $ and $B = \{1\}$ both over the alphabet $\sum = \{0, 1\}.$ Define the function $f : \sum^*\to \sum^*$ as $$ f(x) := \begin{cases} 1,& \text{if}\ w\in A,\\0,&\text{if}\ w\not\in A\end{cases} $$ Observe that $A$ is a context-free language, so it is also Turing-decidable. Thus, $f$ is a computable function. Also, $w \in A$ if and only if $f(w) = 1,$ which is true if and only if $f(w)\in B.$ Hence,$A\leq_m^\mathsf{}B.$ Language $A$ is nonregular, but $B$ is regular since it is finite.

Above example proving that $A$ isn't necessarily regular. But according to Corollary:1, $A$ must be regular. I don't understand where I did make mistake during understanding of theory.


Corollary $2$ is false.

It seems that you are using the implication "$L$ is regular $\implies$ $L$ is decidable" in the wrong direction. If $A \le_m B$ and $B$ is regular, Corollary 1 only tells you that $A$ is decidable, which does not imply that $A$ is regular.


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.