Talk:Mealy machine

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)[reply]

"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)[reply]

On a mealy machine there is an output for each transition from every state. And a Moore machine has an output for every state. So the equivalent Moore machine should have a state for each such transition. These transitions can be uniquely identified by exactly the Cartesian product described above. By the way, you have the Cartesian product wrong: S₀,S₁, and S₂ are not part of it. King Mir (talk) 22:35, 21 November 2010 (UTC)[reply]

I have added this to the Moore machine article. Rp (talk) 15:32, 13 December 2012 (UTC)[reply]

"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:[reply]

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)[reply]

End quote.

Mealy to moore conversion

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

See above.

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)[reply]

A Mealy machine is a deterministic transducer - I have added this to the article. It seems obvious enough not to need proof.Rp (talk) 15:35, 13 December 2012 (UTC)[reply]

I removed this sentence, because I believe it is incorrect, and I don't see any evidence or sources to back it up "However, for each Mealy machine there is an equivalent Moore machine." I believe this would be correct if swapped round... 129.31.242.219 (talk) 10:14, 22 May 2010 (UTC)[reply]

Both are correct. See above. Rp (talk) 15:35, 13 December 2012 (UTC)[reply]

example

Hi. In example section simple example should be shown as a 6-tuple. I can't do it and ask for help. TIA. --Adam majewski (talk) 07:47, 1 October 2011 (UTC)[reply]

Proposed merge with George H. Mealy

This article is the only well known, Wiki-notable contribution of George Mealy. TYelliot | Talk | Contribs 16:20, 16 April 2015 (UTC)[reply]

Oppose merge. Although Mealy machines are his most famous contribution, it's untrue that they're his only notable contribution. I've expanded the Mealy article with other sourced contributions of Mealy and untagged it. —David Eppstein (talk) 04:20, 21 April 2015 (UTC)[reply]

ROM and combinatorial or not

I don't know a way to use a ROM to store machine state. Masked ROMs do not contain flip-flops - I don't remember any type that does. 84.63.77.35 (talk) 07:56, 11 May 2015 (UTC)[reply]

Copyright problem removed

Prior content in this article duplicated one or more previously published sources. The material was copied from: http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Seq/impl.html. Copied or closely paraphrased material has been rewritten or removed and must not be restored, unless it is duly released under a compatible license. (For more information, please see "using copyrighted works from others" if you are not the copyright holder of this material, or "donating copyrighted materials" if you are.)

For legal reasons, we cannot accept copyrighted text or images borrowed from other web sites or published material; such additions will be deleted. Contributors may use copyrighted publications as a source of information, and, if allowed under fair use, may copy sentences and phrases, provided they are included in quotation marks and referenced properly. The material may also be rewritten, providing it does not infringe on the copyright of the original or plagiarize from that source. Therefore, such paraphrased portions must provide their source. Please see our guideline on non-free text for how to properly implement limited quotations of copyrighted text. Wikipedia takes copyright violations very seriously, and persistent violators will be blocked from editing. While we appreciate contributions, we must require all contributors to understand and comply with these policies. Thank you. —Ashley Y 02:24, 21 May 2015 (UTC)[reply]