Promotion Of Language On Semirings Of Finite Automata

The finite automata and the regular languages are very useful [1]. But the finite automata can only receive the regular language. So it is necessary to generalize the traditional finite automata to A<<Σ*>>-finite automata. The method of semi-rings [2]-[14] and formal power series[2][10]-[15] makes finite automata to be used more widely, especially in image compression and speech recognition.In this article we discuss the following three problems.Firstly, the fundamental knowledge of linear algebra is introduced. We begin with the concept of semi-ring, the sequence, star and quasi-inverse of semi-ring and semi-ring identities. Then the definition of the matrix, block matrix and the matrix identities are introduced. Furthermore the formal power series are discussed detailedly and the properties of the semi-ring are generalized to matrix semiring over the semiring of formal power series. Finally the relations between matrix semi-ring over the formal powers series and finite automata are established.Secondly, the finite automata over formal power series semi-ring are introduced. First of all the isomorphism of the Boolean semi-ring and language semi-ring is proved. Base on the languages of semi-ring, the finite automata is generalized in two aspects: the formal definitions of A<<Σ*>>-finite automata and the behavior of A<<Σ*>>-finite automata. Last the power series set identified by A<Σ>-finite automata consists a rationally closed semi-ring is proved.Thirdly, some applications about the A<<Σ*>>-finite automata in the image area are discussed. To start with, I introduce how to denote pixel address of digital image with the word of the alphabet {0, 1, 2, 3}. Then the automaton representation of the image is discussed. Finally the method of approximation for multi-resolution gray level image using A<<Σ*>>-finite automata and the main idea of encoding algorithm for gray level image is given.