Therefore, we have: From the construction of our proper approximations (Proposition 3), we know that only derivations of length log 2 n or greater can be in Z ,n .
0 using the same proof technique we used here, while relying on the fact that C n ( f * n ) ∈ F n , and therefore C n ( f * n )(z) ≤ sN|z| log n. Equipped with the framework of proper approximations as described previously, we now give our main sample complexity results for probabilistic grammars.