Producing Words from a Moore-Automata

Question

Hello,

I would like to ask, "when does a Moore-Automata produce a symbol?". A regular Mealy Machine would of course output symbols on transition and the construction of a Moore Automata clearly shows that the symbol associated with the previous state is output [((s, b), a, b,(s ′ , b ′ )) ∈ R′ :⇔ (s, a, b ′ ,s ′ ) ∈ R implies that it only depends on the previous state]. However I came across the following problem:

On slide 17 of Chapter 7 (Finite State Machines) a Theorem states, that if a Mealy Machine A translates a word a_1,...,a_l to b_1,...,b_l then the equvivalently constructed Moore Machine translates a_1,...,a_l to #,b_1,...,b_l (assuming # is used as the additional symbol). If we now only have an input word of length l and produce symbols on transition we could only output l symbols as far as I can tell - which would result in the automata only producing the word #,b_1,...,b_(l-1) and therefore not being equvivalent, contradiction ?!? How can we solve this? Should we treat it as if the Automata is given a word with an extra symbol appended or allow the output to depend on the "result state" [aka change it to ((s, b), a, b',(s ′ , b ′ )) ∈ R′ :⇔ (s, a, b ′ ,s ′ ) ∈ R which would produce the word b_1,...,b_l (or #,b_1,...,b_l if we count entering the initial state as a transition which I know it isn't)] - or am I missing something obvious again?

As to why this is relevant: In the exam from SS14 question 10 asks for the creation of a FSM which allows the detection of 1011's and 111's in the input sequence - my solution to the above Problem was to make the automata non-deterministic and a transition on the empty word so that a 1 would always be output (and then referring to the initial state in order to add the delay back in). This is however for obvious reasons not-nice, if not wrong.

^ Please correct me if I misunderstood the goal of that exercise (to build a FSM which produces an 'a' once the given sequences were found).

Best regards,

Kevin

Answer 1

Maybe I misunderstand the question, but look at the following: Assume the Mealy machine has the following run 

s0 --a0/b0--> s1 --a1/b1--> s2 --a2/b2--> ...  --an/bn--> s{n+1}

By construction of the Moore machine, we get a Moore machine that will have the following run:

(s0,#) --a0/#--> (s1,b0) --a1/b0--> (s2,b1) --a2/b1--> ... --an/b{n-1}--> (s{n+1},b{n})

By definition, the output of a Moore machine only depends on the state which is the case above, since the trick of the construction is that one stores the output of the Mealy machine as part of the state of the Moore machine and that output is generated one step later as compared with the Mealy machine. 

In the above trace of the Moore machine, I guess that is your problem, you miss the output b{n}. However, you can see that the Moore machine would output that next, and now your doubt is why the Moore machine should do that since there is no further input. 

So, I would say that the difference is to be understood as follows: In a Mealy machine, the output is a reaction to a given input; we cannot produce the output without an input at hand, since the output depends on the inputs. However, in a Moore machine, the output is a reaction of the state change, which is a reaction of the previous input. Hence, a Moore machine *can* produce the output without an input when reaching a new state. Therefore, I would say that the above trace of the Moore machine should actually be completed with another output:

(s0,#) --a0/#--> (s1,b0) --a1/b0--> (s2,b1) --a2/b1--> ...  --an/b{n-1}--> (s{n+1},b{n}) -??/b{n}-->

That way, the automaton will produce the word # b1 b2...b{n} as needed, and that is how the theorem works. Does that answer your question?

Side remark: That is not relevant for the design of reactive systems like hardware circuits since these systems do not terminate. For infinite computations, the above "±1 discussion" is not relevant.

I am not sure whether I understood your solution of the mentioned exercise correctly. But if I am right, and you want to use transitions with the empty word where you produce outputs, then I must say that this is no solution. A reactive system like circuits do always read (one) input and produce (one) output in every reaction step (where one input/output may consist of a vector of values). If you use nondeterminism and epsilon-transitions for the construction, it is fine unless you will finally remove them.

Comments

Maybe have a look at Medwedew automata which are defined as I wrote above.