A Class of Automatic Sequences

Abstract

Let $k\ge 2$. We prove that the characteristic sequence of a regular language over a $k$-letter alphabet is $k$-automatic. More generally, if $t\ge 2$ and $t,k$ are multiplicatively dependent, we show that the characteristic sequence of a regular language over a $t$-letter alphabet is $k$-automatic.

arXiv comment9 pages, 3 figures