# Closure of regular languages under interchanging two different letters

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$$?

• Your approach doesn't work, since the original language could be infinite, while your automaton requires $\binom{n}{2}$ states to handle words of length $n$. – Yuval Filmus Apr 5 at 19:22

## 1 Answer

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) \}$$.
• Thank you for your solution! For the second last specification of the transition functions though, should $\delta'((\sigma, \tau, q, 0), \sigma)$ be $\delta'((\sigma, \tau, q, 1), \sigma)$ instead? – Curious student Apr 6 at 5:47
• Thanks for the correction. – Yuval Filmus Apr 6 at 6:04
• I also was wondering how to prove the correctness of this design (the language accepted by $M'$ is exactly the language accepted by $M$ with two different letters interchanged). I have tried to use induction on the length of strings input, but I cannot find connections using the transition functions. – Curious student Apr 6 at 14:43
• You can use induction. You need to come up with the correct induction hypothesis. – Yuval Filmus Apr 6 at 14:44
• I think induction needs to use interchange as a function to obtain a new regular expression, then prove closure of union, concatenation and Kleene star. Is it more natural for this scenario to just prove $L(M')$ and $interchange(L(M))$ (I made this function up) are a subset of each other using the design of $M'$? – Curious student Apr 6 at 15:42