Black And White Image Compression Automata

Customary expositions of automata theory are often unsatisfactory because that many of the proofs remain inadequate from the mathematical point of view.A very typical example is that one defines a special construction and then just simply claims without proofs that the construction works as intended.In this article,automata theory is developed from ideas about semirings and linear algebra.The tools on linear algebra make many of the proofs computational in nature and consequently and more satisfactory from the mathematical point of view than customary proofs.Besides many of the proofs are much shorter than the customary proofs.The note consists of the following 3 aspects:1. Basic knowledge about linear algebra is introduced.First it begins with the essential concepts of semiring, half mode, sequence, star, qusi-inverse,formal power series and the concerning properties.Then the definition of matrix is discussed.With transfering the properties of semirings to matrices we obtains formal power series matrices.Finally the contact of formal power series matrices and automata is established.2. Automata over the formal power series is discussed. The concept of automata overΣis converted to automata over formal power series.And the identity between automata based on semirings and non-deterministic finite automata is proofed.3. The application of finite automata over semirings in the area of image representation and image compression is given.First how to establish the contact of words and image pixels is introduced. By adding the weights we get the tools discussing grayscale images.Then the relationship of weighted finite automata and multi-resolution images is described.Last some encoding algorithms to prove its usefulness are provided.