# 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?

• Infinite alphabets are very problematic from a language- and automata-theoretic standpoint. Basically, though, what you need to handle this is something like set descriptors on transitions (I'd hesitate to even call these things languages). So you might label a transition $\{\gamma \gamma \mid \gamma \in \Gamma \}$, where $\Gamma$ is your "alphabet". Of course, then, there's no effective procedure for determining that you ought to take this transition, even though you and I know you would. – Patrick87 Oct 23 '13 at 13:42
• Your question is too imprecise. Since there are apparently letters outside $C$, what is the alphabet $A$ containing $C$? And more importantly, how are $C$ and $A$ given? Are they countable? – J.-E. Pin Oct 23 '13 at 18:30
• How can a Turing machine "trivially" recognise this language? Turing machines have finite alphabets so you'll need some kind of coding. – David Richerby Oct 23 '13 at 23:10

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.
• Another good reason to use $A$ for the Alphabet. :=) – J.-E. Pin Oct 24 '13 at 8:54