The aim of this lecture is to present the current state of alphabetic coding theory and its relations to the probabilistic information theory. The presentation deals with fundamental problems of information compression. The main requirement on coding is considered: that of bijectivity of the coding scheme f_v for the language L. Only regular languages, i.e. those that are representable by finite automata, are considered. A brief survey of research results on the decoding complexity of the language L optimal coding matrix M(L) is also included.

alphabetic coding, regular language, finite automaton, information compression

Mathematical problems and theory of numerical methods