Abstract machine that can recognize repetition

Let $C$ be an infinite set of characters. I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$.

For example, if ${x,y,z} \subset C$, and $k = 3$, it should recognize $xxx$ but not $ddd$ or $xyz$. (The same char must be repeated.)

Since $C$ is infinite, a finite state machine cannot recognize this. A Turing machine trivially can. But we don't anything like the power of a Turing machine; simply extending the FSM with a single register that points to a member of $C$ is enough.

My question is: What's the simplest formal abstract machine that is powerful enough to recognize this? Is there a standard extension to FSM's that enables them to recognize this? If I have more complicated versions of this machine (e.g. Move from state 2 to state 3 if you encounter a $k$ repetition of a $C$ char), what's the best way to express them?

There is a generalization of NFAs in which the transitions are labeled with regular expressions. (They are equivalent to NFAs and DFAs.) You can represent "twice the same letter" by $\sum_{\sigma \in \Sigma} \sigma^2$. Of course, such expressions are not standard, but if you want a succinct representation, this is one.

StackExchange Computer Science Q#16362, answer score: 2