A popular approach to reduce power consumption is to identify {\em self-loops} in a state transition graph (STG) of a finite state machine(FSM) followed by gating the clock with a suitable function to power down the circuit (implementation of the FSM) during the self-loop cycles. Although this approach is effective in circuits with plenty of self-loops, it fails for FSMs without self-loops.Since self loops may not be inherently present in a given FSM, we decompose it into interacting FSMs such that they have plenty of self-loops. In this paper, we present a novel partitioning algorithm to decompose a given finite state machine. By using this approach, we could save upto {\bf 71\%} of the total power on circuits like {\bf fetch}, where techniques described could not save any power.