Power reduction can be achieved by turnig off portions of circuits that are idle. Unlike previous work which focused only on either controller or data-path, we propose a decomposition technique that takes both controller and data-path into consideration where, in the former, the state probability of an FSM provides the execution frequency of operations in that state. And, in the latter, operations performed in states provide the information of resource requirements which can be used to determine the resource sharing among states. The goal is to synthesize circuits such that the sub-machine with small area (data-path and controller) will be turned on most of the time (high state probability) and all other parts are turned off. Our experimental results show that on average, 10% area reduction and 24% power reduction can be achieved as compared with designs without decomposition.