Welcome to MathOverflow

Question

0

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

edited Jul 22 2011 at 3:13

asked Jul 22 2011 at 2:23

XL
379●1●7

Noah Stein · Accepted Answer · 2011-07-22 02:31:50Z UTC

3

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.

answered Jul 22 2011 at 2:31

Noah Stein
4,351●1●9●26

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 Jul 22 2011 at 3:21

1

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 2011 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 Jul 22 2011 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 Jul 23 2011 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 2011 at 9:25

show 3 more comments

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.