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

In summary, the conversation discusses a complex finite state machine and the importance of creating a table to account for every possible input and state. The speaker also mentions an instance where a mistake in the table caused issues in a real-life project. The conversation highlights the efficiency and flexibility of using tables in implementing FSMs.
  • #1
r0bHadz
194
17
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.
 

Attachments

  • finiteStateMachine.png
    finiteStateMachine.png
    31.7 KB · Views: 200
Last edited by a moderator:
Physics news on Phys.org
  • #2
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
 
  • Informative
  • Like
Likes anorlunda and r0bHadz
  • #3
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.
 
Last edited:
  • #4
r0bHadz said:
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.

r0bHadz said:
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. :sorry:

Cheers,
Tom
 
  • Like
Likes r0bHadz
  • #5
Tom.G said:
Cheers,
Tom

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

1. What is a finite state machine?

A finite state machine is a mathematical model used to describe the behavior of a system or process. It consists of a set of states, transitions between states, and actions or outputs associated with each state.

2. How does a finite state machine detect overlapping strings?

A finite state machine can detect overlapping strings by using a set of rules or patterns to analyze a sequence of characters. As the machine reads each character, it moves through a series of states and checks for specific patterns or conditions to determine if the string overlaps with another.

3. Can a finite state machine that doesn't terminate still accurately detect overlapping strings?

Yes, a finite state machine that doesn't terminate can still accurately detect overlapping strings. As long as the machine is designed to handle infinite input, it can continue to analyze and detect overlapping strings without terminating.

4. What are some practical applications of a finite state machine that detects overlapping strings?

Some practical applications of a finite state machine that detects overlapping strings include file compression algorithms, spell checkers, and pattern recognition software. These applications rely on the ability to detect and analyze patterns in a sequence of characters.

5. Is it possible for a finite state machine to detect overlapping strings in real-time?

Yes, it is possible for a finite state machine to detect overlapping strings in real-time. With efficient programming and hardware, a finite state machine can analyze and detect overlapping strings as they are being input, making it a useful tool for applications that require real-time processing.

Similar threads

Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
2
Replies
54
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
17
Views
5K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
832
  • Engineering and Comp Sci Homework Help
Replies
7
Views
713
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
  • Electrical Engineering
Replies
6
Views
944
  • Programming and Computer Science
Replies
2
Views
769
Back
Top