Many real-world systems operate and make decisions using limited resources in dynamically changing environments, where the changes can be unpredictable. In this paper, the Restricted Finite State Machine is defined, and its optimality studied; it is a composed finite state machine with input restrictions that can handle limited resources. Then, the Recomposable Restricted Finite State Machine is defined, and its optimality investigated; it can handle unpredictably dynamically changing environments, by reacting to environment changes. In general, the local optimal policies do not generate the global optimal policy of the Recomposable Restricted Finite State Machine and global optimality cannot be achieved without knowledge of future. Thus, a heuristic method, Limited Breath First Search, is developed. The numerical simulation results indicate that the heuristic method performs well with proper parameters, and also indicates that local sub-optimal solutions can be better than the local optimal policies for the global policy/solution of Recomposable Restricted Finite State Machines.