Talk:Mealy machine

From Wikipedia, the free encyclopedia

Contents 1 Mealy/Moore Equivalence 2 "Cryptography" 3 Mealy to moore conversion 4 Transducer

[edit] Mealy/Moore Equivalence

"every Mealy machine is equivalent to a Moore machine whose state is the Cartesian product of the Mealy machine's current and previous states" what the hell does it mean? i know what a Cartesian product is, but i just dont see how it got someting to do with it...

i've done some modificationsm that should provide better context. also, having a section for one example seemed a little weird, so i used the image on the top of the page. i also added a paragraph about cryptographical purposes of mealy machines. however, their main purpose is to describe sequential circuits, but i don't know enough about that. somebody should add a paragraph about that then modify the one with cryptography, to "Also mealy machines can be use to...". hope i helped --Amenzix 12:17, 17 July 2006 (UTC)

"However, for each Mealy machine there is an equivalent Moore machine whose states are the union of the Mealy machine's states and the Cartesian product of the Mealy machine's states and the input alphabet."

This doesn't make any sense to me... So for the Mealy machine pictured, the set of states in the equivalent Moore machine is supposedly {S₀,S₁,S₂,(S₀,0),(S₀,1),(S₁,0),(S₁,1),(S₂,0),(S₂,1)}? I don't think so... Feel free to restore it if you can convince me otherwise. --203.206.183.160 08:18, 30 October 2007 (UTC)

[edit] "Cryptography"

I removed the section below from the article, as it seems to me to be either too unclear to too technical to understand. -- Karada 22:49, 9 May 2006 (UTC) Quote:

A Mealy machine can be used as a cryptographic machine. Given an alphabet A, it is said to be possible to process a word from this alphabet into a word from alphabet B if there exists a Mealy machine which does this. Using mathematical notation, M - Mealy machine, -> - to process: thus a tuple (M, ->). Clearly there exists a Mealy machine which transforms word from alphabet A to the same word, that is there exists a reflexive Mealy machine: a -> a

Also there exists a transitive Mealy machine, that is given two Mealy machines it is possible to construct the third which acts as the the other two connected in series (output from the first is fed into the second and the output from second is output of this Mealy machine): a -> b and b -> c then a -> c.

These two mathematical qualities introduce preordering on set of words which Mealy machines process. Now we can introduce ordering, that is given a class of words it is said that the words are in the same class if a -> b and b -> a. A word which can only be a -> b, but not b -> a is clealy of higher complexity. So Mealy machines can be used to analyse complexity of words which brings us to cryptography.

Hi,

As per my knowledge, the Mealy machine is a simple state machine whose next state transition depends on its current inputs and current outputs as well as its current state. Hence the Mealy machine had a feed back input as well and therefore does require a memory element for its operation to store feedback values —Preceding unsigned comment added by Rock02021985 (talk • contribs) 05:48, 2 April 2008 (UTC)

End quote.

[edit] Mealy to moore conversion

Someone should write a section on this sometime. Fresheneesz 02:56, 15 December 2006 (UTC)

[edit] Transducer

Fresheneesz has brought to my attention that "transducer" might be to broad a word in this case. I must admit that the only thing that I based my claim on "mealy machines" being transducers was on the finite state machine article. "Finite state transducer" is, of course, what I meant. Nevertheless, a quick google of "Finite state transducers"[1] reveals that:

Transducers are automata that have transitions labeled with two symbols. One of the symbols represents input, the other - output. Transducers translate (or transduce) strings. In automata theory (see [HU79]) they are called Mealy's automata.

This seems to mean that mealy machines are the same thing with transducers. However, on the "Finite state machine" article on Wikipedia, it is said that Moore machines are also a FST. Given that that some other references on the internet seem to say the same thing, I guess the FSM article should be changed in this way, I will post this matter on the FSM talk page, and see the result. For now I will change this article accordingly. - Amenzix 22:48, 13 January 2007 (UTC)