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?

BTW, I found that there is not the set of final states in the definition of Mealy machines or Moore machines. On the other hand, final states do exist in the definition of FST, although Mealy machine is one type of FST. Does it mean that final state is not important when we are talking about the Mealy machines?

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you tried finding a problem one can solve but not the other? $\endgroup$
    – Raphael ♦
    Oct 11, 2017 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$
    – Blanco
    Oct 11, 2017 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$
    – Blanco
    Oct 12, 2017 at 5:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2017 at 1:14
  • $\begingroup$ @rus9384 I see now. No, NFST cannot be determinised because of output, not input. $\endgroup$
    – Evil
    Oct 15, 2017 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, 2017 at 2:27
  • $\begingroup$ It is too broad statement, but yes. $\endgroup$
    – Evil
    Oct 15, 2017 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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