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

  • $\begingroup$ 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$. $\endgroup$ Apr 5, 2021 at 19:22

1 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) \}$.
  • $\begingroup$ 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? $\endgroup$ Apr 6, 2021 at 5:47
  • $\begingroup$ Thanks for the correction. $\endgroup$ Apr 6, 2021 at 6:04
  • $\begingroup$ 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. $\endgroup$ Apr 6, 2021 at 14:43
  • $\begingroup$ You can use induction. You need to come up with the correct induction hypothesis. $\endgroup$ Apr 6, 2021 at 14:44
  • $\begingroup$ 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'$? $\endgroup$ Apr 6, 2021 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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