A lower bound for the coding cost and the asymptotically optimal coding of stochastic context-free languages

We consider a language generated by a stochastic context-free grammar with unique derivation for which the matrix of first moments is indecomposable, nonperiodic, and its Perron root is strictly less than one. For such a language we obtain an unimprovable lower bound for the binary coding cost. We also construct an algorithm for asymptotically optimal coding.