Affiliations: Chair of Computer Science, Nizhni Novgorod State Pedagogical University, 1, Uljanova St., Nizhni Novgorod, 603600, Russia. nspu@unn.ac.ru
Note: [] Address for correspondence: Chair of Computer Science, Nizhni Novgorod State Pedagogical University, 1, Uljanova St., Nizhni Novgorod, 603600, Russia.
Abstract: We investigate questions, relating to optimal binary coding of a language, for which a probability distribution is given on its words (for a stochastic language). As optimal we understand the coding, which gives minimum of mathematical expectation of a length of the coded word, or minimum of the coding cost. For any stochastic language with a finite value of the entropy we establish lower and upper bounds of the optimal coding cost, dependent only on the entropy, and we prove their unimprovability. For any stochastic context-free language with unique derivation it is found necessary and sufficient condition of existence of finite values of the optimal coding cost and the entropy. Also an effective method of calculation of the entropy is found for the case when the considered condition holds.
