For example I have 2 simple FSM. I will use regular expression for clarity.

FSM1 = 1+ = [1,11,111,...]
FSM2 = 2+ = [2,22,222,...]
FST = 1/2 = [1->2,11->22,...]

What is the general way to prove that there exists finite-state transducer that maps each string from the set defined by FSM1 to a string defined by FSM2? What is the algorithm to construct such transducer?

I want to have the next properties from mapping:

  1. ๐‘‡(๐ฟ(๐น1))=๐ฟ(๐น2), where ๐ฟ(๐น1) is the regular language accepted by the first FSM, ๐ฟ(๐น2) the one for the second FSM, ๐‘‡ is some transducer

  2. ๐‘‡ is bijective mapping from ๐ฟ(๐น1) to ๐ฟ(๐น2)

  3. It have to specifically map the ๐‘–th string from ๐ฟ(๐น1) to the ๐‘–th string from ๐ฟ(๐น2) using lexicographic order

  • 1
    $\begingroup$ What properties do you want the mapping to have? A mapping that maps every input to 2 would appear to meet all of your stated requirements, but I doubt you'll be happy with that, so I suspect some requires are missing or not clearly stated. Do you want $T(L(F_1)) = L(F_2)$, where $L(F_1)$ is the regular language accepted by the first FSM and $L(F_2)$ the one for the second FSM, and $T$ is some transducer? Do you want $T$ to be a bijective mapping from $L(F_1)$ to $L(F_2)$? Does it have to specifically map the $i$th string from $L(F_1)$ to the $i$th string from $L(F_2)$? in what ordering? $\endgroup$
    – D.W.
    Apr 16 '21 at 19:27
  • $\begingroup$ Please edit the question to clarify. $\endgroup$
    – D.W.
    Apr 16 '21 at 19:27
  • $\begingroup$ @D.W. thank you for a good remarks. I have made edits. $\endgroup$
    – Oleg Dats
    Apr 18 '21 at 11:53

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.