International Journal of Mathematics and Mathematical Sciences
Volume 11 (1988), Issue 2, Pages 355-364
doi:10.1155/S0161171288000420
On rational solution of the state equation of a finite automaton
Department of Computer Science, Eastern Michigan University, Ypsilanti 48197, MI, USA
Received 21 January 1987; Revised 25 June 1987
Copyright © 1988 R. Chaudhuri and H. Höft. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
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.