Moore Machine for a Given Case

Thread Starter

zulfi100

Joined Jun 7, 2012
629
A computer game generates ‘1s’ and ‘0s’. These are associated with awards. The first ‘1’ (i.e. the first 1 of an uninterrupted sequence of 1's obtained by continuously running the program several times such that each execution generates a 1 output in that set of executions) results in 4 awards but the remaining 1’s do not result in any award. On the other hand, each odd numbered 0 results in 2 points and each even numbered 0 does not get any award. For the output 011100001011.. of executions results in awards 2400202024240……

Can we construct a transducer to do the above computation? If yes show it. Otherwise explain why?
We can't because its infinite sized machine. However if the string is finite we can construct a Moore machine attached.Two point one point Machine.jpg :

Some body please guide me if the above Moore Machine/transducer correct or not?

Zulfi.
 

WBahn

Joined Mar 31, 2012
24,987
If you are designing Mealy and Moore machines, then it is always taken for granted that you have a finite-length input sequence since infinite sequences are the province of theoretical computer science (and even there it is a case that is almost always excluded).

Your diagram doesn't define a start state. Don't make your readers assume which state the system starts in.

Assuming you machine starts in the upper-left state, then your machine is close, but not quite there.

Imagine that you have processed the first N outcomes. What is everything that you need to know about all of those prior outcomes in order to know what to do with the next outcome? Each different situation requires its own state because that is how the system keeps track of that information.
 

WBahn

Joined Mar 31, 2012
24,987
Your description of the game doesn't seem to match the example you gave:

For the output
011100001011
2400202024240……

You have six zeroes and six ones, but your reward string has thirteen elements. You seem to be giving rewards of 2 on zero number 1, 2, and 4 and then on one numbers 4 and 5. You are giving awards of 4 on one number 1 and then the last zero and the last one in the sequence.

Don't make us waste time figuring out what you meant to put. Please look it over and make the necessary corrections.

Also, for the zeroes, is the even/odd from the beginning of the string, or just from the beginning of each run of zeroes?
 

Thread Starter

zulfi100

Joined Jun 7, 2012
629
Hi,
Sorry for wrong last statement. Correcting the last statement of question:

"For the output 0111000001011.. of executions results in awards 2 4 0 0 2 0 2 0 2 4 2 4 0……"

2 4 0 0 2 0 2 0 2 4 2 4 0……
0 1 1 1 0 0 0 0 0 1 0 1 1......

For 0s we are counting from the beginning of the string.
From previous reply:

<Imagine that you have processed the first N outcomes. What is everything that you need to know about all of those prior outcomes in order to know what to do with the next outcome? Each different situation requires its own state because that is how the system keeps track of that information.>

We need to know the total points obtained after N outputs of the game, the current state we are in.

If you have something important, please let me know.

Zulfi.
 

WBahn

Joined Mar 31, 2012
24,987
Hi,
Sorry for wrong last statement. Correcting the last statement of question:

"For the output 0111000001011.. of executions results in awards 2 4 0 0 2 0 2 0 2 4 2 4 0……"

2 4 0 0 2 0 2 0 2 4 2 4 0……
0 1 1 1 0 0 0 0 0 1 0 1 1......

For 0s we are counting from the beginning of the string.
If you are counting outputs from the beginning of the string, then why are you awarding 2 points to both the 1st zero and the 2nd zero but not the 3rd zero?

The first step in solving a problem is understanding the problem. This is also usually the hardest part of solving the problem. You clearly aren't at that point yet, so take the time and make the effort to be sure that your understanding of the problem is correct.

<Imagine that you have processed the first N outcomes. What is everything that you need to know about all of those prior outcomes in order to know what to do with the next outcome? Each different situation requires its own state because that is how the system keeps track of that information.>

We need to know the total points obtained after N outputs of the game, the current state we are in.
Okay. After N outputs of the game the total number of points is 8 and we are in state-3. The next round resulted in a 1. How many points are awarded?

If you can't answer that question, then you haven't adequately answered the one you were asked.

What information do you need to know in order to determine what to do with the next outcome?

You answer should be in the form of something like: "I need to know what the prior result was." Or perhaps something like, "I need to know what award the prior result yielded."
 

Thread Starter

zulfi100

Joined Jun 7, 2012
629
Hi,
Thanks for giving time to my prob.
<If you are counting outputs from the beginning of the string, then why are you awarding 2 points to both the 1st zero and the 2nd zero but not the 3rd zero>

Question states that:
On the other hand, each odd numbered 0 results in 2 points and each even numbered 0 does not get any award.

<Okay. After N outputs of the game the total number of points is 8 and we are in state-3. The next round resulted in a 1. How many points are awarded?>
If its a 1, we would get 4 awards if the previous input was 0, or no awards if the previous input was 1.
I think what you are saying in general terms is that I have to create a table having inputs 1 & 0 (as row headers) and states as columns headers. I have to give distinct name to all states. I have to provide a column for 'Total Awards also.

Zulfi.
 

WBahn

Joined Mar 31, 2012
24,987
Hi,
Thanks for giving time to my prob.
<If you are counting outputs from the beginning of the string, then why are you awarding 2 points to both the 1st zero and the 2nd zero but not the 3rd zero>

Question states that:
On the other hand, each odd numbered 0 results in 2 points and each even numbered 0 does not get any award.
So, again, why does your example award 2 points to he second zero and none to the third?

<Okay. After N outputs of the game the total number of points is 8 and we are in state-3. The next round resulted in a 1. How many points are awarded?>

If its a 1, we would get 4 awards if the previous input was 0, or no awards if the previous input was 1.
But you don't know if the previous input was 0 or 1 because you didn't say that that was one of the things that you had to remember. So the bottom line is that you haven't specified what you need to keep track of well enough to be able to determine whether you get a reward or not. But you HAVE identified (whether you recognize it or not is a different matter) at least one piece of information that you need to keep track of -- whether the prior input was a 0 or a 1.

I think what you are saying in general terms is that I have to create a table having inputs 1 & 0 (as row headers) and states as columns headers. I have to give distinct name to all states. I have to provide a column for 'Total Awards also.
Forget about the damn machine for a minute and focus on understanding the problem and what information YOU would need to know what to do.

If the ONLY information you were going to have when you get the next input in the sequence is the answer to a few yes/no questions and, based ONLY on those answers and the next input you had to determine what the number of awards was going to be, what would those questions be?
 
Top