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.

  • 1
    $\begingroup$ What have you tried? $\endgroup$
    – Yamar69
    Oct 21 '19 at 18:40
  • $\begingroup$ 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 $\endgroup$ Oct 21 '19 at 21:39
  • $\begingroup$ Not all decidable languages are regular. For example, the language $\{a^nb^n \mid n \geq 0 \}$ is decidable but not regular. $\endgroup$
    – siracusa
    Oct 22 '19 at 4:21
  • $\begingroup$ 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? $\endgroup$ 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


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.