# Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $$f$$ that maps strings over $$\{a, b, c\}$$ to strings over $$\{0, 1\}$$ by replacing each $$a$$ by 0, each $$b$$ by 0, and each $$c$$ by 1. For example $$f(cabbc) = 10001$$. The function $$f$$ extends naturally to languages: if $$L$$ is a language over $$\{a, b, c\}$$, then $$f(L)$$ is the language over $$\{0, 1\}$$ defined as $$\{f(w) \mid w\text{ is in }L\}$$.

Prove that if a language $$L$$ is decidable, then so is $$f(L)$$.

I am thinking that since $$L$$ is decidable it must be regular so there exists a DFA for $$L$$. $$f(L)$$ is closed -- dk how to prove though. Then $$f(L)$$ is also regular. Therefore is also decidable.

• What have you tried? – Yamar69 Oct 21 '19 at 18:40
• I am thinking that since L is decidable it must be regular so there exists a dfa for L. f(L) is closed -- dk how to prove though. Then f(L) is also regular. therefore is also decidable – Sunita Jain Oct 21 '19 at 21:39
• Not all decidable languages are regular. For example, the language $\{a^nb^n \mid n \geq 0 \}$ is decidable but not regular. – siracusa Oct 22 '19 at 4:21
• can you please explain reason why do you think that $L$ is decidable implies $L$ is regular. Or are you talking about some specific $L$ like $0^+$ or something like that? – Vimal Patel Oct 22 '19 at 12:31

Let $$f$$ be any computable mapping such that $$|f(x)| \geq c|x|$$ for some $$c > 0$$. For every language $$L$$, if $$L$$ is computable then so is $$f(L)$$.
To see this, let us be given an input $$y$$. We go over all strings $$x$$ of length at most $$|y|/c$$. For each of them, we check whether $$x \in L$$ and $$f(x) = y$$. If we found such a string $$x$$, then $$y$$ is in the language, otherwise it isn't.