Some Topics Of Finite Automata

Actually the theory of automata is an very active research field in the world,and has been widely used in mathematics,computer science,linguistics,artificial intelligence and so on.This work mainly studies the related properties of finite automata from the following four aspects:1)Polynomial subsequences of Thue-Morse and Rudin-Shapiro sequences:the sequences generated by finite automata are called automatic sequences,which have relatively small sub word complexity.For two classical automatic sequences——Thue-Morse sequence and Rudin-Shapiro sequence,we show that their polynomial subsequences of degree≥ 2 have maximal subword complexity,hence these subsequences are no longer automatic.2)A conjecture of Shallit about Apery-like numbers:put where v3 is the 3-adic valuation.Shallit put forward in 2000 about the recurrence relationship of b(n).We have established this conjecture by using an identity of Barnes.As a corollary,we show that the sequence(b(n))n≥0 is 3-regular.3)Arithmetic properties of finite automata:when he studied in 2004 the factorization of finite automata,Jia-Yan Yao introduced the notion of prime automata and discovered their properties,then he asked whether prime automata existed.In this work,we classify finiye automata by graph theory,and show that none finite automata is prime.4)Opacity of finite automata:for an information communication system,its inherent noise can be characterized by opacity.We study the opacity of composite automata system under d∑ metric,and compute the opacity of composite system composed of Ising automata.