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

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?

• Are the $k$ repetitions of the input string marked by separators? Or are they simply concatenated as a single string? Nov 14, 2018 at 21:08
• Also, simply adding $/varespilon$ transitions everywhere does not cut it since you may end up recognizing strictly more strings. Nov 14, 2018 at 21:11
• Regarding epsilon transitions - you are right, that made me doubt my reasoning. I don't have anything specific in mind, so I'd be happy to know about results in both options (with and without separators). Nov 14, 2018 at 21:21
• Also two-way finite state automata (that may walk back and forth over the input string) are not more powerful than ordinary FSA. Two-way automata can be "programmed" to do a fixed number $K$ of passes over the string. Nov 15, 2018 at 8:44

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.

• Thanks for the answer. Can you please elaborate regarding the idea of "Each vector...represents the result of performing the transitions starting at the state corresponding to the position of the element in the vector"? Nov 14, 2018 at 21:59
• @user1767774: Does that help?
– rici
Nov 14, 2018 at 22:48