A random walk on a regular language is a Markov chain on the set of all finite words from a finite alphabet whose transition probabilities obey the following rules:
It will be shown that the -step transition probabilities of such a
process must obey one of 3 distinct types of asymptotic behavior. This
will be accomplished by the analysis of an algebraic system of
generating functions related to the Green's function of the random
walk. Possible extensions of the main theorem to Markov chains whose
Green's functions are not algebraic will be discussed, along with
connections to other combinatorial problems of interest in theoretical
computer science.