2

I have a homework question:

Construct a Moore machine that takes a string consisting of a's b's and c's as input and outputs a string containing 1 at the end of each substring abc and a 0 in all other positions. e.g. input, aabcb produces output, 000010

I tried constructing, but I have come to a dead end. Here is my attempt: enter image description here

As you can see, I can't create a string cccb and an 'abc' can output a 0. I feel like I overcomplicated this simple problem.

EDIT: Took a break and redid it. I think this is right, unless someone can tell me otherwise:

enter image description here

Leo
  • 565
  • 5
  • 20

2 Answers2

2

The solution. Just needed to think clearly.

The solution

Leo
  • 565
  • 5
  • 20
0

I'll try to help you without spoiling an answer:

  • Why do you use a second cycle (the lower triangle)?
  • How would you implement a machine that halts successfully after finding a subsequence?
  • What do you need to do to keep it running indefinitely? Convince yourself that an error to match a subsequence is equivalent to the initial state.

I've solved it using only four states, but maybe there's a solution with just three. It should be clear that you can't get better than that.

Bruno Kim
  • 2,300
  • 4
  • 17
  • 27
  • I'm sorry, I do not follow. Can u tell me which 2 states of mine would you eliminate? The reason I have the cycle is because if I wanted multiple c's or b's. – Leo Aug 24 '14 at 21:23
  • Why do you need to detect multiple b's and c's? You should only care for the 'abc' substring. – Bruno Kim Aug 24 '14 at 21:26
  • if I want abbbbccccaababccccc? – Leo Aug 24 '14 at 21:28
  • That would produce almost only zeros, except for the 'abc' before the final stream of c's, according to my interpretation of the question. It only asks that the exact substring 'abc' outputs a 1. – Bruno Kim Aug 24 '14 at 21:31
  • Could u please show me what you mean! I've been battling with this for a while. :) – Leo Aug 24 '14 at 21:37
  • First, try the second bullet point: how would you implement a substring matcher for 'abc'? That is, given the string `aabbccabcaaa`, it would halt at `aabbccabc|aaa` in a successful state, as it just read 'abc' exactly. All other states are failures, including the initial one. – Bruno Kim Aug 24 '14 at 21:43
  • I think I solved it. Check my question after my edit. I think I've got it. Thanks :) – Leo Aug 24 '14 at 22:09