The Semirings Method For Pushdown Automata

Automata theory and the closely related theory of formal languages form nowadays such highly developed and diversified body of knowledge. Customary expositions of automata and language theory are often unsatisfactory in the sense that entirely different ad hoc proofs are given in very similar situations; moreover, many of proofs still remain inadequate from the mathematical point of view. A typical example of the latter state of affairs is that one defines a certain construction and then simply claims without proof that the construction works as intended. The pushdown automata are introduced by using the method of semirings and the tools from linear algebra, That bulid the connection between semirings algebraic systems of equations and the automata. This makes the discussion of pushdown automata more simply.First gives an introduction to research objects which inculding pushdown automata and semirings and provides a background and a motive for our study.Then discusses the concept of formal power series, and convert the concept of semirings to formal power series . Then transfers semirings into matrix in the foundation f of the concept of matrix . Finally gives the linear system that relates solution of matrix star .Later proofs language semirings and boolean formal power series semirings are isomorphic. On the basis of transfering language semirings semirings into language matrix semrings defines the pushdown transition matrix then define pushdown automata and the behavior of the pushdown automata in matrix semirings.