Properties Of The Recoded Languages And Sequences

This thesis studies some properties of the recoded regular languages and sequences. Language is a string set of a alphabet . The so-called re-coding to languages and sequences is to change the alphabet which they depend in with certain rules. Regular language is the language that can be recognized by finite automaton, also defined to the language generated by regular grammars, such language has important applications in the field of theoretical computer. Sturmian sequence is the aperiodic sequences ove binary alphabet of minimal conplexity, the earliest researchers on the Sturmian sequence is Hedlund and Morse, the definition is given by Coven and Hedlend in 1973. Such sequences are widely used in many applications, such as: game theory, automata, dynamic systems, diophantine approximation, and computer graphics and so on.This thesis discusses the complexity function of Sturmian sequence which be changed from binary alphabet to ternary alphabet , and tries to discuss the complexity function of Tribonacci sequence which be changed from binary alphabet to ternary alphabet . This thesis also gives some conditions on whether the language is regular after number system is changed.In the preparation section, we introduce the definitions and properties of the language, automata, regular languages and Sturmian sequences, and give some conclusions on them, discusse the relationship between language and Sturmian sequences in the third chapter, and then study the complexity function of the re-coded sequence. Finally, we give a necessary condition and a sufficient condition on whether the language is regular after the number system is changed, and give the detailed proof on related conclusions.