Regarding FSM's, remember that you often can split them into several FSM's if they get too big. That reduces complexity immensily if possible.