Large Language Models (LLMs) have shown remarkable capabilities across various applications but struggle with sequential decision-making tasks like planning. This work demonstrates that integrating LLMs with Finite-State Machines (FSMs) can enhance their reasoning and planning abilities, while also offering increased reliability. Several setup variants are compared, providing a better understanding of how validations, feedback loops, and restrictions enhance robustness and effectiveness. A comparison to the well known Chain-of-Thoughts approach is also provided. Our methods improve planning capabilities of all analysed LLMs, consistently increasing the success rate in solving tasks of varying complexities. A detailed analysis of the two best variants are provided, highlighting their respective strengths and weaknesses.