Abstract We consider a generalization of the problem of counting ternary words of a given length which was recently investigated by Koshy and Grimaldi [10]. In particular, we use finite automata and ordinary generating functions in deriving a k -ary generalization. This approach allows us to obtain a general setting in which to study this problem over a k -ary language. The corresponding class of n -letter k -ary words is seen to be equinumerous with the closed walks of length n − 1 on the complete graph for k vertices as well as a restricted subset of colored square-and-domino tilings of the same length. A further polynomial extension of the k -ary case is introduced and its basic properties deduced. As a consequence, one obtains some apparently new binomial-type identities via a combinatorial argument.