On the generating sequences of regular languages on k symbols
Marie-Pierre Béal, Dominique Perrin · Journal of the ACM · 2003
The main result is a characterization of the generating sequences of the length of words in a regular language on k symbols. We say that a sequence s of integers is regular if there is a finite graph G with two vertices i, t such that s n is the number of paths of length n from i to t in G . Thus the generating sequence of a regular language is regular. We prove that a sequence s is the generating sequence of a regular language on k symbols if and only if both sequences s = ( s n ) n ≥0 and t = ( k n − s n ) n ≥0 are regular.