# How to prove existance and construct finite-state transducer between two different FSM?

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

• 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? – D.W. Apr 16 at 19:27
• Please edit the question to clarify. – D.W. Apr 16 at 19:27
• @D.W. thank you for a good remarks. I have made edits. – Oleg Dats Apr 18 at 11:53