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$ – Sunita Jain 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$ – 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.

| cite | improve this answer | |

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.