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 automaton M to have a rational solution is that the lexicographical Gödel numbers of the strings belonging to each of the end-sets of M form an ultimately periodic set. A method of determining the existence of a rational solution of the state equation is also given.
Link to Published Version
Chaudhuri, R., & Höft, H. (1988). On rational solution of the state equation of a finite automaton. International Journal of Mathematics and Mathematical Sciences, 11(2), 355–364. doi:10.1155/S0161171288000420