0
$\begingroup$

What is the conditional probability or probability of classes of languages?

Let $E,C,S,F,R $ be the class of computably enumerable languages,computable languagesl,context-sensitive anguages,context-free languages and regular languages respectively. $E$ is class of all computably enumerable languages and it's subset of $E$ is the Cantor space,take the uniform probability measure on the Cantor space,then what is the probability or conditional probability $P(C),P(S),P(F),P(R),P(S|C),P(F|C),P(R|C),\cdots,P(R|F)$ ?suppose L is selected randomly under the fair-coin (Lebesgue-Cantor) measure on $2^{\omega}$.

$\endgroup$

1 Answer 1

3
$\begingroup$

The probability measure you're asking about is nonatomic, but your events of interest are countable. Therefore the unconditional probability of each is zero, and the conditional probabilities are undefined.

$\endgroup$
8
  • $\begingroup$ Mr.Stein,thank you.yes,the the unconditional probability of each is zero.but the main question is the conditional probability.I have edit the post as appending "suppose L is selected randomly under the fair-coin (Lebesgue-Cantor) measure on $2^{\omega}$. $\endgroup$ Jul 22, 2011 at 3:21
  • 1
    $\begingroup$ Probability conditioned on measure zero events is not well-defined. I also don't understand your addition because you already mentioned the measure was the uniform measure on Cantor space. $\endgroup$
    – Noah Stein
    Jul 22, 2011 at 11:36
  • $\begingroup$ I just clarify what I have said in other way Since I do not know why you said the conditional probabilities are undefined or not well-defined. I understand now why you think the conditional probabilities are undefined. $\endgroup$ Jul 22, 2011 at 13:28
  • $\begingroup$ @Mr.Stein.then how do you think about the conditional probability of $P(F|R)$?I think $P(F|R)=1$,although $P(R)=0$? $\endgroup$ Jul 23, 2011 at 5:06
  • $\begingroup$ Sure, it would be natural enough to define $P(F\mid R) := 1$, but that does not make it clear that the other conditional probabilities make sense. $\endgroup$
    – Noah Stein
    Jul 23, 2011 at 9:25

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.