3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\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$ Commented Apr 5, 2021 at 19:22

1 Answer 1

Reset to default
1
$\begingroup$

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.