3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are the $k$ repetitions of the input string marked by separators? Or are they simply concatenated as a single string? $\endgroup$ – dkaeae Nov 14 '18 at 21:08
  • $\begingroup$ Also, simply adding $/varespilon$ transitions everywhere does not cut it since you may end up recognizing strictly more strings. $\endgroup$ – dkaeae Nov 14 '18 at 21:11
  • $\begingroup$ 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). $\endgroup$ – user1767774 Nov 14 '18 at 21:21
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Nov 15 '18 at 8:44
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – user1767774 Nov 14 '18 at 21:59
  • $\begingroup$ @user1767774: Does that help? $\endgroup$ – rici Nov 14 '18 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.