I have implemented a small state machine in this way (in pseudo code):

class Input {}

class KeyInput inherits Input
{ 
   public :
     enum { Key_A, Key_B, ..., }
}

class GUIInput inherits Input
{ 
   public :
     enum { Button_A, Button_B, ..., }
}

enum Event { NewGame, Quit, OpenOptions, OpenMenu }

class BaseState
{
   String name; 
   Event get_event (Input input);
   void handle (Event e); //event handling function
}

class Menu inherits BaseState{...}
class InGame inherits BaseState{...}
class Options inherits BaseState{...}

class StateMachine
{
   public :

      BaseState get_current_state () { return current_state; }

      void add_state (String name, BaseState state) { statesMap.insert(name, state);}

      //raise an exception if state not found
      BaseState get_state (String name) { return statesMap.find(name); } 

      //raise an exception if state or next_state not found
      void add_transition (Event event, String state_name, String next_state_name)
      { 
         BaseState state = get_state(state_name);
         BaseState next_state = get_state(next_state_name);

         transitionsMap.insert(pair<event, state>, next_state);

      }

      //raise exception if couple not found
      BaseState get_next_state(Event event, BaseState state) 
      { 
         return transitionsMap.find(pair<event, state>); 
      }

      void handle(Input input) 
      { 
         Event event = current_state.get_event(input)
         current_state.handle(event);
         current_state = get_next_state(event, current_state);

      }

   private :

      BaseState current_state;
      map<String, BaseState> statesMap; //map of all states in the machine

      //for each couple event/state, this map stores the next state
      map<pair<Event, BaseState>, BaseState> transitionsMap; 

}

So, before getting the transition, I need to convert the key input or GUI input to the proper event, given the current state; thus the same key 'W' can launch a new game in the 'Menu' state or moving forward a character in the 'InGame' state;

Then I get the next state from the transitionsMap and I update the current state

Does this configuration seem valid to you ? Is it a good idea to separate states and transitions ?

And I have some kind of trouble to represent a 'null state' or a 'null event'; What initial value can I give to the current state and which one should be returned by get_state if it fails ?