Finite state machine that doesn't terminate and detects overlapping strings

[r0bHadz]

Homework Statement:

Create a finite state machine that recognizes the input strings “a”, “abc” and “cab” by
outputting a 1 (otherwise output 0 for the input).
The input alphabet is {a, b, c}. The output alphabet is {0, 1}.
The input stream may be any length, beginning with any arbitrary sequence of the input
alphabet.
The FSM should be completely specified. The FSM must include both inputs and outputs
for each transition.

The FSM should not terminate.
The FSM should recognize overlapping tokens (input strings).

Relevant Equations:

An FSM is an abstract representation of behavior
exhibited by some systems.

Attached is what I have so far. I believe it is done but I am not 100% sure.

It seems to me like every case is considered. For each state, and output of a,b, or c is possible.

 

[Tom.G]

I like your colored state diagram, makes it much easier to follow.

I think you missed ABCABC.
You correctly found the overlapping:
A...Q1
ABC...Q1,Q2,Q3,Q5
.AB... Q6

But missed the second ABC at Q6
Also what happens if the first character is C?

There may be others, I haven't looked.

A trick I learned for complex FSMs is to create a table. There is a column for each input variable and a row for each state.

Every table location must have an entry for the Output Value when that entry is matched and the Next State to branch to. If there is an empty entry you have not completed the specification.

Cheers,
Tom

 

[r0bHadz]

You are a legend Tom. I was just going through it but I don't think I would have caught that. Good eye, man. I appreciate ya!

edit: I'm not sure what you mean exactly if the first character is C. If you mean the input string starts with a c, then it goes from state q_0 to state q_4

Also, if you complete the table, that does not mean that your specification is correct, right?

edit:
Just found out there is a lot more actually.

 

[Tom.G]

edit: I'm not sure what you mean exactly if the first character is C. If you mean the input string starts with a c, then it goes from state q_0 to state q_4

So it does! I missed that one.

Also, if you complete the table, that does not mean that your specification is correct, right?

Right. You still may not have created enough states. It does encourage taking account of every possible input in every state though. When implementing an FSM in computer code, or even in dedicated hardware, table look-ups are fast and easy to change.

One project I was on was controlling fluid transfer on a medium sized tank farm. There was an instance where I had the pumps starting before all the valves were open. You could hear the pipes knocking and pressure relief valves banging all over the several acre property. Oops! The on-site fix took less than a half hour, just changed three table entries to open the valves first. Much easier than trying to patch a string of IF-THEN statements. The documentation and source code updates back in the office took rather longer.

Cheers,
Tom

 

[r0bHadz]

Cheers,
Tom

Sounds intense Tom! Cool to see that this stuff is used in the real world.