On rational solution of the state equation of a finite automaton

[摘要] We prove that the necessary and sufficient condition for the state equation of a finite automatonMto have a rational solution is that the lexicographical Gödel numbers of the strings belonging to each of the end-sets ofMform an ultimately periodic set. A method of determining the existence of a rational solution of the state equation is also given.

[学科分类] 数学（综合）