1
$\begingroup$

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

$A/B=\{w \mid \exists z\in B\land 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 semi-decidable languages, prove that $A/B$ is semi-decidable

$\endgroup$
2
$\begingroup$

Let us keep this in mind: $w\in A/B \iff \exists z\in B: wz\in A$

Since we are working with semi-decidable machines, then we have no problem iterating over all $z$'s until we find a good one!

Therefore, the idea to solve it will be the following: Let $M_A$ be the TM for $A$, and let $M_B$ be the TM for $B$.

We want to create a new TM for $A/B$ like so:(when given $w$ as input)

  • Iterate through all $z\in \Sigma^*$
  • For each such $z$, if both $M_B(z)$ and $M_A(wz)$ accepted, then accept.

Notice, that there is still an important detail left! What happens if $M_B(z)$ never stops? We will never continue to search the other $z$'s!

To solve that, we will modify the TM as follows:

  • Let $T=\{\}$ be an empty set representing the set of all running "threads" we have created
  • For $z\in \Sigma^*$:
    • Create two new threads that will compute $M_B(z)$ and $M_A(wz)$ respectively. Add those two threads into $T$.
    • Do one step in every thread in $T$.
  • If at any point, there is some $z$ such that both threads $M_B(z)$ and $M_A(wz)$ have finished executing and both accepted, then accept as well.

This solution effectively runs the machine $M_B(z_0)$ (for a specific $z_0$) only one step for each new $z$ that we discover - instead of trying to run the machine until it halts. This allows us to continue to discover more new $z$'s even if the execution of those machines never ends!

I will leave it to you to verify that this machine really accepts $A/B$ :)

$\endgroup$
0

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.