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 a: over a fixed finite alphabet , selects a contest-free grammar G(x) representing x in the sense that x is the unique string belonging to the language generated by G(x), Lossless co mpression of a: takes place indirectly,ia compression of the production rul es of the grammar G(x), It is shown that, subject to some mild restrictions , a grammar-based code is a universal code with respect to the family of fi nite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing gram mar-based codes are presented.