Results 1 to 7 of 7
  1. #1
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default Help needed to create an Automata state machine in Java

    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

  2. #2
    travishein's Avatar
    travishein is offline Senior Member
    Join Date
    Sep 2009
    Location
    Canada
    Posts
    684
    Rep Power
    6

    Default

    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.

  3. #3
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    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 :(

  4. #4
    travishein's Avatar
    travishein is offline Senior Member
    Join Date
    Sep 2009
    Location
    Canada
    Posts
    684
    Rep Power
    6

    Default

    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,
    Java Code:
    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);    
      }
    }
    Attached Thumbnails Attached Thumbnails Help needed to create an Automata state machine in Java-state_diagram.jpg  

  5. #5
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    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?

  6. #6
    travishein's Avatar
    travishein is offline Senior Member
    Join Date
    Sep 2009
    Location
    Canada
    Posts
    684
    Rep Power
    6

    Default

    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
    Java Code:
    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.

  7. #7
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    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.
    Last edited by maz09; 02-07-2010 at 04:36 PM.

Similar Threads

  1. Replies: 0
    Last Post: 06-10-2008, 07:37 AM
  2. Some help needed: 2D Cellular Automata
    By markus-sukram in forum AWT / Swing
    Replies: 1
    Last Post: 04-27-2008, 08:02 PM
  3. Replies: 1
    Last Post: 03-17-2008, 12:59 AM
  4. Concurrent Hierarchical State Machine 4.3
    By levent in forum Java Software
    Replies: 0
    Last Post: 08-03-2007, 04:44 PM
  5. Virtual machine of java.
    By Albert in forum Advanced Java
    Replies: 1
    Last Post: 07-05-2007, 08:48 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •