Do multiple transitions over the input give finite state machines more power?

Question

In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state to another without reading a character. However, the movement over the input string is still unidirectional.

Is there a formal model of a FSA that reads the input string K times, and only then reaches its final state? is this model more powerful than FSA, e.g., can it recognize context-free languages that are not regular?

I think the option of adding an epsilon transition for every transition edge in the FSA means the models are equivalent in power (since we can model K iteration over the input by epsilon transitions from the last state back to the first -- although I am not sure), but if this is so, are there any results regarding the number of states needed in a regular FSA and a FSA with K transitions?

Answer 1

Multiple passes do not add any power.

It's possible to do all the passes in parallel, using a state machine whose states are vectors of states in the original machine. Each vector has one element for each state in the original machine, and represents the result of performing the transitions starting at the state corresponding to the position of the element in the vector. A vector state is an accepting state iff there is a path of length $k$ starting at the original machine's starting state and linking the state at each position to that position.

Specifically, let the original machine be $(Σ, Q, q_1, δ, F)$, where $Q = \{q_1, \ldots, q_n\}$. Define the new machine $(Σ, Q^n, q'_s, δ', F')$ with

$$\begin{align} q'_s &= \langle q_1, \ldots, q_n\rangle \\ \delta'(\langle q_{i_1},\ldots,q_{i_n}\rangle, s) &= \langle \delta(q_{i_1}, s),\ldots,\delta(q_{i_n}, s)\rangle \\ \langle q_{i_1},\ldots,q_{i_n}\rangle \in F' &\text{ iff } \exists t_1,\ldots,t_k \text{ with } t_1 = 1, q_{t_k} \in F \text{ and } t_j = i_{t_{j-1}} \text{ for } j \in \{2,\ldots,k\} \end{align}$$ Although that's a lot of states, it's still a finite number, and the set of accepting states is well-defined and can be enumerated. So the multiple-pass machine is still a finite-state machine.