Closure of regular languages under interchanging two different letters

Question

Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For example, if $M$ only accepts $101$, $M'$ should only accept any element from $\{011, 110\}$.

Suppose a string accepted by $M$ has $n$ letters, I tried to construct an FSA with a parallel structure, with initial state $q_0$ that has $\epsilon$ transition to $M_1, M_2, \dots, M_{\binom{n}{2}}$, where each $M_i$ accepts strings with two letters at two unique positions interchanged. The final states should be $F_1, F_2,\dots,F_{\binom{n}{2}}$. Then I may claim that $M'$ should accept their union.

But I am not sure how to construct this parallel structure. Specifically, how should I construct the transition function of this parallel structure that restricts a single interchange only for any $M_i$?

Answer 1

Suppose that you guess that $\sigma$ and $\tau$ should be exchanged, where $\sigma$ appears before $\tau$ (in the original word).

You start reading the input word, letter by letter. When you encounter $\tau$, you can optionally act as if you read $\sigma$. Later on, when you encounter $\sigma$, you can optionally act as if you read $\tau$. From that point on, you accept the word if the original DFA accepted it.

Here is how to implement this in an NFA. Let the original DFA have states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct a new NFA whose states are $\Sigma \times \Sigma \times Q \times \{0,1,2\}$. The initial states are $\{(\sigma,\tau,q_0,0) : \sigma \neq \tau\}$. The final states are $\Sigma \times \Sigma \times F \times \{2\}$. The most complicated bit is the transition function $\delta'$:

• For $\kappa \neq \tau$, $\delta'((\sigma,\tau,q,0),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),0) \}$.
• $\delta'((\sigma,\tau,q,0),\tau) = \{ (\sigma,\tau,\delta(q,\tau),0), (\sigma,\tau,\delta(q,\sigma),1) \}$.
• For $\kappa \neq \sigma$, $\delta'((\sigma,\tau,q,1),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),1) \}$.
• $\delta'((\sigma,\tau,q,1),\sigma) = \{ (\sigma,\tau,\delta(q,\sigma),1), (\sigma,\tau,\delta(q,\tau),2) \}$.
• $\delta'((\sigma,\tau,q,2),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),2) \}$.