×

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
PDF BibTeX XML Cite