1
$\begingroup$

I think I can't understand the meaning of language being decidable. The next case makes no sense to me:

Considering I have language L1 which is regular, and language L2 which is in RE\R (in particular, it cannot be decided).

The right-division of any regular language with some language is regular, and in particular in R.

so:

L1/L2={x ∈ Σ* | ∃ y ∈ L2 : xy ∈ L1}

is decidable.

But I can't see why. I can't describe an algorithm that decides L1\L2, so how come this language is decidable? I know how to define the transition function, but does it means that the language is decidable? After all, I can also define a transition function to the accepting problem, it still does not make it decidable.

After all, to check if x belongs to L1 \ L2 I need to go over words and check if there is a word in L2 that completes x to a word in L1, but if there is none, I will run forever.

I think I'm missing something, so I'm very confused. Would appreciate help!

$\endgroup$
2
$\begingroup$

In fact, if $L_1$ is regular then $L_1/L_2$ is regular for any $L_2$.

Indeed, consider a DFA for $L_1$ with transition function $\delta$ and accepting states $F$. We modify the set of accepting states to $$ F' = \{ q : \delta(q,w) \in F \text{ for some } w \in L_2 \}. $$

You might object that "$F'$ cannot be computed". So what? We never said that you can compute a DFA for $L_1/L_2$ given one for $L_1$ and some reasonable representation of $L_2$. All we claim is that $L_1/L_2$ is regular.

Check out this question for a similar but simpler situation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But if it can be computed, I can also define a function that decides problems like the halting problem and claim that the halting problem is decidable. (I have read the question you added but I still can’t understand) $\endgroup$ – Ella Jun 14 at 4:42
  • $\begingroup$ I don’t see how you can solve the halting problem this way. The issue is that there are infinitely many possible Turing machines. $\endgroup$ – Yuval Filmus Jun 14 at 6:01

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.