3
$\begingroup$

There are several versions of the definitions of the FST and the Mealy machine. Some of the definitions are almost same. Some have a little differences. But it seems that they both are a kind of DFA with an output function $G \colon \Sigma \times Q \rightarrow \Gamma \times Q$, where $\Sigma$ is the input alphabet and $\Gamma$ is the output alphabet.

I'm not sure about the differences between them.

Are they the same machines? Why is there two different names?

$\endgroup$
  • $\begingroup$ Have you tried finding a problem one can solve but not the other? $\endgroup$ – Raphael Oct 11 '17 at 19:29
  • $\begingroup$ I tried some examples written in the books and I failed. It makes me think that they are the same. Since I do not know the differences between the definitions, it is hard to find one. Actually, it seems that no one compares with them. Also, different versions of definitions make me confused. $\endgroup$ – TeamBright Oct 11 '17 at 19:43
  • $\begingroup$ "Introduction to The Theory of Computation" by Michael Sipser says that the FST do not have a set of accept states $F$. It also says that "a finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject". And I think that the usefulness of $F$ is trivial here, Is that right? $\endgroup$ – TeamBright Oct 12 '17 at 5:45
  • $\begingroup$ @Evil Thanks for your answer, you partially solve my problem. So the key of the differences is the accepting states. It can let the FST be non-deterministic and it can be used to solve a partial function. I just want to know which machine is more powerful. For example, maybe the Mealy machine cannot distinguish the functions with different domains. Actually, an exhaustive answer may be better for this question, I think. $\endgroup$ – TeamBright Oct 13 '17 at 16:22
1
$\begingroup$

Mealy machine (by G. Mealy) is a deterministic finite state transducer with output associated with transition (edge) instead of state. It could handle multiple inputs and multiple outputs but by definition cannot be non-deterministic. According to definition it must be defined for all possible combinations of states and inputs.

Finite State Transducer is a generalization of Finite State Machine (M. Rabin, D. Scott) which can be both deterministic and non-deterministic. The output is associated with states, not all combinations of states and input must be present. Not all NFST can be determinized.

The computational power of both is equal in the Chomsky hierarchy, but there exist machines that cannot be expressed by other type. In special transduction hierarchy FST is higher than Mealy.
There are extensions to create nondeterministic Mealy machines, but nondeterminism for transducers is not really exploited, it would generate the family of outputs when one is really needed, unless it was the goal then NFST wins here.

From physical point of view it makes difference, Mealy equivalent machines are shifted in time, but considering only the result it does not matter.

$\endgroup$
  • $\begingroup$ Wait, if NFST recognizes only REG languages, it can be determized. Something is wrong here. Or what do you mean? $\endgroup$ – rus9384 Oct 15 '17 at 1:14
  • $\begingroup$ @rus9384 I see now. No, NFST cannot be determinised because of output, not input. $\endgroup$ – Evil Oct 15 '17 at 2:05
  • $\begingroup$ So, when we are saying about functional finite problems, non-determinism can't be simulated by deterministic FST? But if problem is decision it can? $\endgroup$ – rus9384 Oct 15 '17 at 2:27
  • $\begingroup$ It is too broad statement, but yes. $\endgroup$ – Evil Oct 15 '17 at 3:59

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.