CODEWITHSUNDEEP
javafsmstate-machine
akmal elias
akmal elias

Reputation: 1

How to create Finite State Machine In Java

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

Upvotes: 0

Views: 3022

Answers (2)

posthumecaver
posthumecaver

Reputation: 1863

Well this is an old question but for the people who stumbles on here, while nobody mentioned here, I will advice to check two existing frameworks before you implement you own State Machines with Java.

One is Spring State Machine, which you can model your State and Events as Java DSL or better use tools like Eclipse Papyrus. Most of you are familiar with Spring framework, which allow us to use several features of Spring like dependency injection and everything else that Spring can offer.

It is really great for modelling the lifecycle of an Apparat, with states like INITIALIZING, STARTED, ERROR, RECOVERING, SHUTTINGDOWN, etc.. but I see lots of people are trying to model a Shopping Chart, a Reservation System with it, the memory footprint a Spring State Machine is relatively big to model millions of Shopping Charts or Reservations.

One other disadvantage, with Spring State Machine, while has a capability to persist itself for long running processes but it does not have any mechanism to adapt to changes in these processes, if you persist a process and you have to recover it lets say 10 days later with a changed happened in the business process because of a new software release / requirements, you have no built in means to deal with it.

I have several blogs, blog1 blog2, demonstrating how you can program Spring State Machine, specially model driven way if you want to check it.

But mainly because the disadvantages I mentioned before, I advice you to look another framework first, Akka FSM (Finite State Machine) which is more fitting with its low memory footprint to have millions and millions of instances and has a capability to adapt changing long running processes.

Now you can develop with Akka framework with Java but believe me because of some missing language elements, you don't want to read the code, Scala is a much more fitting language to develop with Akka with its Case Classes (which will like lots of similar to Java Enumeration) and powerful pattern matching capabilities with Switch statements in Scala.

Now I hear you saying Scala is too complex, I can't convince my project leads to develop with Scala, to convince you all this is an option, I developed a Proof of Concept application using a Java/Scala hybrid with all Scala Akka Finite State Machine code generated from an UML model, if you want to check it out here the links to the blogs, blog3 blog4.

I hope this information would help you.

Upvotes: 0

The Beruriah Incident
The Beruriah Incident

Reputation: 3257

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. :) )

Upvotes: 2

Related Questions