Can an object oriented program be seen as a Finite State Machine?

Question

This might be a philosophical/fundamental question, but I just want to clarify it.

In my understanding a Finite State Machine is a way of modeling a system in which the system's output will not only depend on the current inputs, but also the current state of the system. Additionally, as the name suggests it, a finite state machine can be segmented in a finite N number of states with its respective state and behavior.

If this is correct, shouldn't every single object with data and function members be a state in our object oriented model, making any object oriented design a finite state machine?

If that is not the interpretation of a FSM in object design, what exactly people mean when they implement a FSM in software? am I missing something?

Thanks

Answer 1

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.

Answer 2

The issue is not whether something "is" or "isn't" a finite state machine. A finite state machine is a mental model that may be useful for understanding something if that thing can be thought of as one.

Typically the finite state machine model applies to things with a small number of states, such as a regular grammar, or the instruction sequencer of a computer.

Answer 3

To answer your question directly: almost certainly not. There doesn't appear to be a formal mathematical theory for OOP the way that lambda calculus and/or Combinatory Logic underly functional programming, or Turing Machines underly ordinary old imperative programming.

See this stackoverflow question for more.

My guess is that the lack of an underlying mathematical theory is why everybody knows what an "object" is when they see one, but nobody sees "objects" quite the same as anyone else.

Answer 4

No, not practically anyway. A finite state machine normally only remembers one piece of data: its current state.

A typical application of an FSM is lexing or parsing. For example, when we're doing lexing, it's (normally) fairly easy to encode the actions for every possible input in terms of a current state, and the value of the input.

For example, we might have a NUMBER state in which we're reading the digits of a number. If the next character we read is a digit, we stay in the NUMBER state. If it's a space or tab, we'd return the digits and then progress to some WHITE_SPACE state, or something on that order.

Now, it's certainly true that in a typical FSM (especially one that's implemented in software) we end up with bits and pieces that technically don't quite fit an FSM mixed in with the FSM itself. For example, when we're reading digits of a number, you're frequently going to save the position of the first digit, so when you get to the end you can easily compute the value of the number.

The FSM itself, has some limitations -- it has no counting mechanism. Consider, for example, a language that used "/" to start a comment and "/" to end a comment. Its lexer would probably have a COMMENT state that it entered when it saw a '/' token. It has no way at this point (short of adding another state like COMMENT2) to detect another "/" and realize that it's dealing with a nested comment. Rather, in the comment state, it'll recognize */ as telling it to leave the comment state, and anything else leaves it in the comment state.

As mentioned, you certainly could include a COMMENT2 state for a nested comment -- and in that, a COMMENT3 state, and so on. At some point, however, you're going to get sick of adding more states, and that will determine the maximum nesting depth you allow for comments. With some other form of parser (i.e., not a pure state machine, but something that has some memory to let it count) you can just track your nesting depth directly, so you stay in the COMMENT state until you reach a close comment token that balances up the first one, so your counter goes back to 0 and you leave the COMMENT state.

As I said, however, when you add a counter like that, what you have is no longer truly an FSM. At the same time, it is actually pretty close -- specifically, close enough that you can simulate the counter by just adding more states.

In a typical case, however, when somebody talks about implementing an FSM in software, they'll keep it reasonably "pure". In particular, the software will react to the current input based only upon the current state, and the value of the input itself. If the reaction depends on much of anything else, they usually won't call it a state machine (at least if they know what they're talking about).

Answer 5

I don't believe the accepted answer is completely correct.

You cannot model an arbitrary program written in a Turing Complete language, whether it is object-oriented or not, as a Finite State Machine. Almost all modern computer languages, such as Java, C++, or Smalltalk, are Turing Complete.

For instance, you cannot create a Finite State Machine to recognize a sequence of objects where you have n instances of one object followed by n instances of another object because Finite State Machines are incapable of writing n to a variable. They can only read input and switch to a state.