1
$\begingroup$

I am self-studying formal languages and want to solve an example problem. Given formal languages $A,B\subset\Sigma^*$ over an alphabet $\Sigma=\{a,b,c\}$ with $$A=\{\omega\in\Sigma^*\vert\left|\omega_a\right|=\left|\omega_b\right|=\left|\omega_c\right|\}$$ and $$B=\{a^ib^jc^k\vert i,j,k\in\mathbb{N}\}$$ where $\left|\omega_n\right|$ denotes the number of $n$s in the word $\omega\in\Sigma^*$, I want to prove that $A$ is reducible to $B$, i.e. that there exists a computable (total) function $f:\Sigma^*\rightarrow\Sigma^*$ for which it holds that $\omega\in A\iff f(x)\in B$ for all words $\omega\in\Sigma^*$.

I think a suitable function would be given by $f(\omega):=abca^{\vert\left|\omega_a\right|-\left|\omega_b\right|\vert}b^{\vert\left|\omega_b\right|-\left|\omega_c\right|\vert}$, for which the required equivalence obviously holds. But it is not clear to me how I would best prove that this function is (Turing-)computable. Do I have to produce an explicit Turing machine which takes a word $\omega$ as input and outputs $f(\omega)$, or is there a more straightforward way? Also, is there a way to intuitively see that this function is computable?

$\endgroup$
4
  • $\begingroup$ Both languages are computable, so there is such a function -- that's a rather easy lemma. The proof is illustrative; a suitable $f$ is completely boring. See also here; despite the different setting, the answer is literally the same. (If your problems can be solved by functions that are not more powerful than the reduction, this always works.) $\endgroup$
    – Raphael
    Mar 23, 2018 at 14:25
  • $\begingroup$ @Raphael How do I prove that the function $f$ I gave is computable though. I want to understand this as well. $\endgroup$
    – azureai
    Mar 24, 2018 at 13:13
  • $\begingroup$ @Raphael In fact, this was my primary question. I only wrote down the rest of the exercise to provide context. Should I edit the question, make a new one, or can you answer me here in the comments please. $\endgroup$
    – azureai
    Mar 24, 2018 at 14:40
  • $\begingroup$ I see. "Do I have to produce an explicit Turing machine which takes a word ω as input and outputs f(ω), or is there a more straightforward way?" -- that's the definition, so yes. Helpful lemmas may exist, and depending on your level you may be willing to hand-wave more or less. Basically, give an algorithm at the appropriate level of precision that computes $f$. $\endgroup$
    – Raphael
    Mar 25, 2018 at 16:55

0

Browse other questions tagged or ask your own question.