The Study Of The Sequences Generated By Infinite States Automaton,k-regular Sequences And Their Corresponding Issue

In this dissertation, we concern some special sequences and their regularity. We expand substitutions over a finite alphabet and finite automata to substitutions over an infinite alpha-bet and automata with infinite states. Moreover, we study the regularity of the sequences which are generated by them. At last, we discuss some properties of the sum-free sets in number theory, we mainly focus on their regularity.Specifically, three classes of regular sequences are discussed in this dissertation care-fully:One of them is the sequence{(?)logb(an+?)?}?0.We use the regularity of some language to prove that the sequence is fr-regular if and only if ? ? Q. The second one is the sequences generated by both substitutions over an infinite alphabet and automata with infinite states. Comparing them with substitutions over a finite alphabet and finite automata, we study the regularity of the sequences generated by them. As well as character their reg-ularity are invariant under some codings of linear recurrence. We have known the relation between the regular sequences and the automatic sequences:a sequence is ?-regular and takes on only finitely many values if and only if it is a ?-automatic sequence. According to this fact, we also give another effective tool for proving sequences not automatic. The other one is the sum-free sets generated by Cantor-like sequences and some substitution se-quences, Such sum-free sets considered as integer sequences are 2-regular. We also prove that zero-one sequences corresponding to certain sum-free sets are automatic.Let ?,? be real numbers and b?2 be an integer. Allouche and Shallit showed that the sequence{[?n+??}>o is b-regular if and only if a is rational. In Chapter 3, utilizing a base-independent regular language, we prove a similar result that the sequence{|logb (?n+ ?)?}n?0 is-regular if and only if a is rational. In particular, when ?=(?),?= 0 and b= 2, we answer the question of Allouche and Shallit that the sequence{|1/2+log2n?}n?0 is not 2-regular, which has been proved by Bell, Moshe and Rowland respectively.In Chapter 4, we define substitutions over an infinite alphabet and automata with infi-nite states. We study their combinational properties and prove that some regular sequences can be generated by them. Moreover, we state some conditions which are contributing to non-regularity of some sequences generated by them. For some sequences, we prove that their regularity are invariant under some codings. At the end of this chapter, we put forward some development and prospect about automata with infinite states, and state some simple conclusions.Cameron introduced a bijection between the set of sum-free sets and the set of all zero-one sequences. In Chapter 5, we study the sum-free sets of natural numbers corresponding to certain zero-one sequences which contain the Cantor-like sequences and some substitution sequences, etc. Such sum-free sets considered as integer sequences are 2-regular. We also prove that sequences corresponding to certain sum-free sets are automatic.In the last chapter, we summarize the main results. Then, we come up with some further questions corresponding to our topics.