# 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