Finite State Machine Reset Signal FPGA
In an FSM it is a good idea to two states, one for the asynchronous reset and one for the reset and define them so there is no room for the synthesizer to generate hardware without them. 

Use an asynchronous reset if the clock is not available at power up (which is determined by your power and clock design) this will allow the state machine to be set to a known state while the clock is not running. If your designing the schematic, make sure you follow guidelines for generating a clean async signal (if it doesn't have a clean rise time this can create metastablity problems).

You should always have a synchronous reset to memory elements to set the element to a known state. 

The code (for memory) look like this (for VHDL). I'm too lazy to write an FSM so I'll copy this counter in to illustrate (just change the counter logic to an FSM (FSM's are very similar to counters):

DACCLK_CNT : process( ARST_L, SYS_CLK)
begin
  if ARST_L = '0'  then
    DAC_COUNT &lt;= 0;
  elsif rising_edge(SYS_CLK) then
    if DAC_START_H = '1'  or DAC_RST_H = '1'  then
      DAC_COUNT &lt;= conv_std_logic_vector(10#0#, 5);
    elsif (DAC_COUNT &lt; conv_std_logic_vector(10#21#, 5) )     then
      DAC_COUNT &lt;= DAC_COUNT + 1;
    else
      DAC_COUNT &lt;= DAC_COUNT;
    end if;
  end if;
end process;


ARST_L is an asynchronous reset, and is not gated by the clock. In this particular design it goes high as the power comes on, thus resting everything to a known state. 

DAC_RST_H is a clocked reset, and sets the counter (or FSM to a known state).