FSM are the solution to a lot of coding problems that in the beginning just look like bunch of if..thens. Of course, there are a lot of problems that scream "FINITE STATE MACHINE" in their definition, but I'd say that applying FSM early on as a sort of "preemptive optimization" can save a lot of headaches.
For example an ecommerce order tracking system with different status (in cart, paid, shipped, returned, so on). Spree solves it very elegantly, look at those "events", "transitions".
I also happened to work in a very huge C++ project for the business logic component of a call center, using CORBA and the Reactor pattern from ACE to integrate different parts of the user / ACD / 1st agent / specialist / CTI combo.
But it was a telco project, so the "let's use a FSM" was well thought from the beginning. Turns out you could easily know what the system would do just by reading a huge Smartdraw document, and this also allowed for reasoning on new use case scenarios. It did not matter that the main file was a horrendous 40kLOC C++ class because the Smartdraw diagram was the documentation and everything else was just trivial code.
How is that relevant to the parent's point? Non-determinism has no relation to a system with infinite states, and the NFSM -> FSM construction algorithm provides no help in that case.
