Algorithmic complexity of problems of optimal alphabetical coding for context-free languages

We consider a combinatorial-logical model of alphabetic coding that takes into account the structural properties of the language of the messages. As languages of the messages we consider the closest known extensions of regular languages – context-free (CF) languages and deterministic CF (DCF) languages. For classes of models of alphabetical coding of CF and DCF languages we prove the algorithmic undecidability of one of the basic problems of coding – the problem of optimal coding (in the sense of cost).
We study the theoretical possibility of solving the problem of optimal coding for two forms of restrictions on the complexity of decoding: when decoding with finite delay and with finite-automaton decoding. We show that the restrictions imposed on decoding do not coincide for irregular models of languages and one does not include the other.