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?
Abstract machine that can recognize repetition
formal languages;computability;turing machines;automata;finite automata