Recognizing finite state machines with repetition

Question

I'm interested in finite state automata which have the capacity to require repetition. That is, the machine may be in a state in which the next character may be any character from set $S$, but, whatever character there is, it must be repeated 3 times. Or it may be in a different state, which requires a character from set $T$ repeated twice.

I could in theory make a different state for each character in set S, and for each character in set T. But that overcomplicates things and obscures the pattern - it can be any character in set S, but the same character must be repeated.

Is there any standard approach to this? I'm interested both in terminology and in practical code.

---

Motivation: I do not know the full makeup of the set $S$ or $T$. I'd like to be able to communicate effectively about the FSM, draw state diagrams, and do implementation, without having to define $S$ or $T$. In fact, $S$ and $T$ change based on the scenario. (Now, given a character, it's trivial to tell if it's part of $S$ or $T$ — but, a priori, it's impossible to enumerate them.)

At the least, I'd like a good way to draw a state diagram for these types of machines. Perhaps I should use a standard FSM with some type of annotation? Could state charts help with this?

Answer 1

Finite automata in which the transitions are regular expressions might be the model you are looking at. Indeed you could have transitions of the form $p \xrightarrow{aa + bbb} q$ to indicate that in order to go from $p$ to $q$, you need either 3 $a$'s or 2 $b$'s. This model has the same expressive power as NFAs and DFAs.

Answer 2

(Previously a comment, made into an answer instead)

In finite automata, using additional states is the pattern to what you're asking. Adding scratch, or working, memory may give you something that is formally no more powerful than the FA model, but which is nonetheless different. What you want is like a pizza without any dough: lacking memory, or rather, encoding memory entirely within state information, is the defining characteristic of a DFA. Of course, you could define your own machine model with finite scratch memory and prove it's the same as a DFA, but that's not exactly what you asked.