Not all state machine designs are "unsafe." "Safe" depends on how many states are in a design and how you define the state encoding styles:

"Safe" State Machines

If the number of states (N) is a power of 2 and you use a binary or gray-code encoding algorithm, then the state machine is "safe." This ensures that you have M number of registers where N = 2M. Because all of the possible state values (or register statuses) are reachable, the design is "safe."

"Unsafe" State Machines

If the number of states is not a power of 2, or if you do not use binary or gray-code encoding algorithm (e.g., one-hot), then the state machine is "unsafe."

For example, Figure 1 shows a design that contains four states:

Figure 1: NRZ-to-Manchester Conversion

The number of states is four if you use the one-hot encoding algorithm. For example:

s0 => 0001
s1 => 0010
s2 => 0100
s3 => 1000

Thus there are 12 more states that are not defined. Generally, these states are covered by the "others" (for VHDL) or "default" (for Verilog) branch of the case statement. The default operation of the synthesis tool will optimize away unreachable states in order to get a high-performance circuit. However, the optimization will create an "unsafe" circuit.