0
$\begingroup$

I have found two interesting questions regarding the quotient of languages, described as:

$A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

The first one is:

  • Let $A$ and $B$ be regular languages, prove that $A/B$ is decidable

By using the proof from this other question, it can be proved that $A/B$ is regular if $A$ is regular too.

Then, since any regular language is decidable, $A/B$ will be regular (and decidable) too.

The second one is:

  • Let $A$ and $B$ be decidable languages, prove that $A/B$ is semi-decidable

I have no idea on how to prove this one, I assume that it's somehow related to $A$ and $B$ being able to stop for any string, whether it's accepted or rejected, but since I don't know whether $A$ is regular or not, I don't know what to do.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let $\Sigma$ be your alphabet. You want to design a Turing machine $T$ such that, given any word $w \in \Sigma^*$, $T(w)$ accepts if and only if $w \in A / B$. Notice that since you only want to prove that $A/B$ is semi-decidable, $T(w)$ is not required to reject when $w \not\in A / B$.

Since $A$ and $B$ are decidable, you know that there are two Turing machines $T_A$ and $T_B$ such that that $T_A(x)$ (resp. $T_B(x)$) accepts if $x \in A$ (resp. $x \in B$) and rejects otherwise.

You can then design $T$ as follows:

  • For each word $z \in \Sigma^*$:
    • If $T_B(z)$ accepts and $T_A(wz)$ accepts:
      • Accept.
$\endgroup$
1
  • $\begingroup$ Oh! I see. That was simple...thank you. $\endgroup$
    – Lightsong
    Jan 5, 2021 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.