MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$.

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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}$. – XL _at_China Jul 22 '11 at 3:21
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. – Noah Stein Jul 22 '11 at 11:36
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. – XL _at_China Jul 22 '11 at 13:28
@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$? – XL _at_China Jul 23 '11 at 5:06
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. – Noah Stein Jul 23 '11 at 9:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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