Grammar-Based Codes: A New Class of Universal Lossless Source Codes

We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string x over a fixed finite alphabet, selects a context-free grammar [G.sub.x] representing x in the sense that x is the unique string belonging to the language generated by [G.sub.x]. Lossless compression of x takes place indirectly via compression of the production rules of the grammar [G.sub.x]. It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented. Index Terms--Chomsky hierarchy, context-free grammars, entropy, Kolmogorov complexity, lossless coding, redundancy, universal coding.