Regularities in output trees for words of a stochastic context-free language and a lower bound of the coding cost. Critical case.(Russian)Zbl 1073.68052

Summary: We consider a language generated by a stochastic context-free grammar whose matrix of the first moments is indecomposable, non-periodic, and its Perron root equals 1. For such a language, we establish regularities in output trees of fixed height $$t$$ as $$t\to\infty$$. Basing on these regularities, a sharp lower bound for the binary coding cost is obtained.

MSC:

 68Q45 Formal languages and automata 68Q42 Grammars and rewriting systems