Say I have a finite state transducer, 6 tuple FST with a set of states, input symbols, output symbols, transition function, a start state, and an output function. If I combine the output function into the transition function and create this mutated FST called iFST, where the output happens on the "edges" and just one symbol is outputted each step. Would this new FST still be able to compute the same functions as a normal FST?


It seems your notion is called a Moore machine (output function in the nodes) whereas the other variant is called Mealy machine (output on edges). This is what wikipedia states:

"Every Moore machine $M$ is equivalent to the Mealy machine with the same states and transitions and the output function $G(s, \sigma) \rightarrow G_M(s)$, which takes each state-input pair $(s, \sigma)$ and yields $G_M(s)$, where $G_M$ is $M$'s output function.

However, not every Mealy machine can be converted to an equivalent Moore machine. Some can be converted only to an almost equivalent Moore machine, with outputs shifted in time. "

In another terminology, the transitions of a FST are of the form $(p,a,b,q)\in Q\times \Sigma\times\Delta\times Q$, where, $\Sigma,\Delta$ are the input/output alphabet of the transducer: from state $p$, reading $a$ from input, move to state $q$, writing $b$ to output. Sometimes this is called a Generalized Sequential Machine, and the more general definition of a FST allows $Q\times \Sigma^*\times\Delta^*\times Q$ instead.

Now the transitions of a Moore machine, which in wikipedia formalization [but with my symbols] has a transition function $T : Q \times \Sigma \rightarrow Q$ and output function $G : S \rightarrow \Delta$, can be written in the above FST format like $(\,p,a,G(a),T(p,a)\,)$, for every $p\in Q$, every $a\in\Sigma$.

I do not know what a "normal" FST is. I prefer output on edges (like the input) to make input/output more symmetric.

  • $\begingroup$ I am not sure if this is the same. I was talking about completing removing the output function. If I am not mistaken Mealy machines still have an output function. And by a normal FST what I meant is having an output function. Could I combine the output and transition function and create a "iFST" and have it be able to compute the same functions as a FST $\endgroup$ – Raj Kona Nov 22 '15 at 4:48
  • 1
    $\begingroup$ The issue may have to do with $\varepsilon$-transitions resp. non-determinism in general, which allows us to pick different edges but not necessarily states. That said, "with outputs shifted in time" seems to be a restriction not typically considered in automata theory; there you'd only be interested in the resulting language. $\endgroup$ – Raphael Nov 22 '15 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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