Discussion Of Finite Automata Based On Algebraic Theory Of Semirings

In the classical theory of formal languages and automata, the complex proofs have been resulted in due to the limitations of mathematic tools that were selected and the readability of the proofs is reduced. In this note finite automata will be discussed by the methods of semirings, which will transform the research of finite automata into the discussion of linear equations of semirings by the link between finite automata and linear algebra of semirings to make the proofs of finite autumata more concise and readable. The note consists of three parts as follows.1. The basic knowledge of linear algebra will be introduced. Firstly, the power set semiring will be introduced from the concept of semirings in particular partial semirings, which is also the collection of language. Secondly, semirings and closely related properties will be gradually extended to matrix semirings and the power set matrix semirings will be obtained. Finally, the link will be established between the power set matrix semirings and finite automata.2. The finite automaton based on semirings will be given. To begin with, the identity will be proved between the finite automaton based on semirings and non-deterministic finite automaton. Moreover, the classical methods and closely related theory will be proved by the finite automaton and the properties of regular language will be proved by comparing with the conventional methods. 3. The finite automaton equipped with an output device will be discussed. In order to compare with traditional finite automata, the working principle of the Moore machine and Mealy machine will be given before rational transducer, which will be discussed to make the discussion of finite automata further development.