How to write a program that will read the set of states of FSM. The input data will be from text file with the format (state input next-state) and the last line is final state. for example :
s0 a s1
s1 a s2
s2 a s2
s1
The program output will be:
a) The list of string generated by the FSM.
b) The program can determine whether the FSM is DFA or NDFA and print the result
I'm not going to give you a coded solution, but are some directions of thought.
First of all, FSMs need start states and end states, so you're missing important info.
If you're generating a list of strings, you're probably dealing with a very limited subset of FSMs that accept a finite number of strings. Therefore, it's reasonable to try every possibility; follow every path through the graph, and print whenever you hit an end state.
Think about what differentiates a DFSM from a NDFSM. It's non-deterministic if there are multiple ways to go with some input. So, when you're building your graph, if you ever have a node with two identical transitions to different states, that's non-deterministic. Since any non-determinism makes the entire system non-deterministic, determinism is just the complete absence of non-determinism.
So, you're probably going to want to start with actually creating a representation. Two easy ways come to mind. More visually, you can create a graph. The simplest way to do this is to create a node class, then an object for each node, containing pairs of transitions and destinations.
A way I prefer to represent FSMs is with a hash map/dictionary. Use the node and transition as a key with the destination as the value. That makes navigation fairly easy.
Good luck!
EDIT: In determining non-determinism, don't forget to think about epsilon transitions (like I just did for a second. :) )
