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

Ok , if L is decidable , then some TM machine decides L

Let M be a TM that decides L

Now we construct a TM N that decides f(L) :

N on input w : "

Generate all possible mapped (original) strings x from w by :

1. Replacing all 1s in w by c

2. Replacing all 0s in w by all possible combinations of as & bs

Run M on every x if M accepts any x accept , else reject "

So for ex , w =100 , N generates all possible mapped strings , caa , cab , cba , cbb , if M accepts any of these , then there is a string x , such that f(x) = w and x is in L , if none of them is accepted then we reject