Help needed to create an Automata state machine in Java

[maz09]

Hi all,

im trying to create a finite automata state machine, whereby a state can have several transitions to other states.

Ive tried an implementation where each state was an object from a State class, however, each state had to be constructed using a constructor. This is tedious for a large automata. So i had to scrap that idea.

I used a HashMap structure, but i dont think i understand it fully...

what im trying to create is something as follows:

2 classes:
1.State
2.Transition

based on user input, n amount of states should be created , where n is any integer. (This was not possible when each state was an object).

state class
each state can have several transitions to other states:

ive thought of doing Map<State, List<Transition>> states = new Hashmap <State,List<Transition>();
this way, each state can have an list of transitions...

transition class

Transition has (symbol, state) as it parameters...

the above is what im trying to create, but i would appreciate if someone could advise as to how to create transitions by adding (symbol, state) within the list for each individual state

thanks

[travishein]

Why not have a
Map<State, Map<Symbol,State>>

where the outer map is the state,
the inner map is the transition, where the key is the symbol that would engage the next state.

[maz09]

thanks for your reply.

but wouldnt Map<State, Map<Symbol,State>>, restrict each state to having one transition?

each key is unique, meaning that mapping a state to a <symbol,state> wont be able to have duplicate symbols going to same states. therefore, each state is only able to have a unique transition, which is not what i need.

I need to allow multiple transitions for every state, hence i thought Map<State, List<Transition>> would be a better option? i just dont know how to construct a state using that approach lol :(

[travishein]

well, each state would have one unique transition for a given symbol, but it would support multiple transitions for every state, or even duplicate symbols going to same states. (just not two transitions for the same symbol, from the given state)

consider
S0, S1, S2, S3 as states.

and the transition between states is
S0: {a->S1} {b->S2} {c->S0}
S1: {a->S2} {b->S3} {c->S0}
S2: {a->S3} {b->S0} {c->S0}
S3: {a->S0} {b->S1} {c->S0}

Or pictorially, see attached picture

So,

class State {
  String name;
  
  public State(String aName) {
    this.name = aName;
  }
  
  public String getName() {
    return this.name;
  }

  // and override the equals(), hashcode() methods
}

class Symbol {
  String value;

  public class Symbol(String aValue) {
    this.value = aValue;
  }

  public String getValue() {
    return this.value;
  }

  // and override the equals(), hashcode() methods
}

// maybe this Map would be placed inside a 'machine' class
class Machine {

  Map<State, Map<Symbol, State>> machine = new HashMap<State, Map<Symbol,State>>();

  public void init() {
    // hard coded create the symbols and states for this example.
    State s0 = new State("S0");
    State s1 = new State("S1");
    State s2 = new State("S2");
    State s3 = new State("S3");

    Symbol a = new Symbol("a");
    Symbol b = new Symbol("b");
    Symbol c = new Symbol("c");

    Map<Symbol, State> s0Transitions = new HashMap<Symbol,State>();
    s0Transitions.put(a, s1);
    s0Transitions.put(b, s2);
    s0Transitions.put(c, s0);

    Map<Symbol, State> s1Transitions = new HashMap<Symbol,State>();
    s1Transitions.put(a, s2);
    s1Transitions.put(b, s3);
    s1Transitions.put(c, s0);

    Map<Symbol, State> s2Transitions = new HashMap<Symbol,State>();
    s2Transitions.put(a, s3);
    s2Transitions.put(b, s0);
    s2Transitions.put(c, s0);

    Map<Symbol, State> s3Transitions = new HashMap<Symbol,State>();
    s3Transitions.put(a, s0);
    s3Transitions.put(b, s1);
    s3Transitions.put(c, s0);

    machine.put(s0, s0Transitions);
    machine.put(s1, s1Transitions);
    machine.put(s2, s2Transitions);
    machine.put(s3, s3Transitions);    
  }
}

[maz09]

your reply is much appreciated. Thank you.

However, constructing everything hard coded is long winded when creating a large number of states.

Is there any way of generating a number of states and transitions based on user input?

for example, if the system prompts user for number of states, and they enter 20, 20 states to be created... that wont work using this method of constructing each state individually right?

[travishein]

well, sure, that manual set up state machine like that was just for example that the structure would work.

i mean, in a real use state machine, i would even consider using a database

create sequence state_id_seq;
create table state (
  id bigint not null default next_val('state_id_seq'),
  name varchar(60) not null,
  active boolean not null default true
);
alter table state add constraint pk_state primary key(id);

create sequence transition_id_seq;
create table transition(
  id bigint not null default nextval('transition_id_seq'),
  symbol char(1),  -- or what ever symbol input type is really
  from_state_id bigint not null,
  to_state_id bigint not null,
  active boolean not null default true
);
alter table transition add constraint pk_transition primary key (id);
alter table transition add constraint fk_transition_from_state_id foreign key (from_state_id) references state(id);
alter table transition add constraint fk_transition_to_state_id foreign key (to_state_id) references state(id);

Or, possibly some means to just serialize that map of states and symbols there into a file and reload it.

But this 'model' for how we store states is completely independent of how the states would be created I would think. Such as having a simple console interface asking the user to enter how many states. maybe a menu to enter transitions after, where pick a state from the list of existing states, and then add transition, then it prompts to enter the symbol and the next state. I can envision a GUI dialog or a web form to do this as well.

[maz09]

thanks again.

i basically need to create states, symbols, and transitions based on what the user inputs. The machine created is going to be dynamic. please advise, how I can create a dynamic automata machine based on user inputs, and not create a hard-coded machine.