Any single-threaded program running on a machine with a finite amount of storage can be modelled as a finite state machine. A particular state in the finite state machine will represent the specific values of all relevant storage—local variables, global variables, heap storage, data currently swapped out in virtual memory, even the content of relevant files. In other words, there will be a lot of states in that finite state model, even for quite trivial programs.
Even if the only state your program has is a single global variable of a 32-bit integer type, that implies at least 2^32 (more than 4 billion) states. And that's not even taking into account the program counter and call stack.
A push-down automaton model is more realistic for this kind of thing. It's like a finite automaton, but has a built-in concept of a stack. It's not really a call-stack as in most programming languages, though.
There's a Wikipedia explanation, but don't get bogged down in the formal definition section.
Push-down automata are used to model general computations. Turing machines are similar, but IIRC not identical — though their computation capabilities are equivalent.
Thankyou to kevin cline for pointing out the error above - as Wikipedia also points out, push-down automata are more powerful than finite state machines, but less powerful than Turing machines.
I honestly don't know where this brain fart came from - I do know that context sensitive grammars are more powerful than context free, and that context sensitive grammars can't be parsed using a simple push-down automaton. I even know that while it's possible to parse any unambiguous context-free grammar in linear time, it generally takes more than a (deterministic) push-down automaton to do that. So how I could end up believing a push-down automaton is equivalent to a Turing machine is bizarre.
Maybe I was thinking of a push-down automaton with some extra machinery added, but that would be like counting a finite automaton as equivalent to a push-down automaton (just add and exploit a stack).
Push-down automata are important in parsing. I'm familiar enough with them in that context, but I have never really studied them as computer-science models of computation, so I can't give much more detail than I already have.
It is possible to model a single OOP object as finite state machine. The state of the machine will be determined by the states of all member variables. Normally, you'd only count the valid states between (not during) method calls. Again, you'll generally have a lot of states to worry about—it's something you might use as a theoretical model, but you wouldn't want to enumerate all those states, except maybe in a trivial case.
It is fairly common, though, to model some aspect of the state of an object using a finite state machine. A common case is AI for game objects.
This is also what's typically done when defining a parser using a push-down automaton model. Although there are a finite set of states in a state model, this only models part of the state of the parser—additional information is stored in extra variables alongside that state. This solves e.g. the 4-billion-states-for-one-integer issue—don't enumerate all those states, just include the integer variable. In a sense it's still part of the push-down automaton state, but it's a much more manageable approach than in effect drawing 4 billion state bubbles on a diagram.
Best Answer
There are several variations of the definition of a finite state machine. The one you give is common in CS classes, particularly in regards to formal languages and the theory of parsing. In this context, the FSM is often directly related to a regular expression, and the goal is feed strings into the FSM to see if they match a regular expression.
The set of final states defines which states are final states. They aren't a different sort of thing. Instead of a set of final states, you can instead imagine that some states are simply labeled as final states. Indeed, the having a set of final states is isomorphic to adding a bit to each state indicating whether it is final or not.
The purpose of knowing which states are final is that a string is matched (or accepted) by the state machine if we are in a final state when we reach the end of the string. Without distinguishing final states, every prefix of the input would also be "matched". For example, for a FSM like
1 -a-> 2 -b-> 3,if
3is a final state (and the others are not), then it will (only) match the string "ab". If all are final states then it would match the strings "", "a", and "ab".Beyond parsing, many problems can fit in this mold especially when we consider variations such as allowing infinite streams of input and adding output to states and/or transitions. This move allows FSMs to do more than just match things, but even matching can be more powerful than you might think (e.g. see model checking). Examples include describing protocols, communicating processes, game logic, fraud detection, business processes, and also doing model checking, hardware synthesis, and orchestration. Physical systems may also be partially modeled by finite state machines.