Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
6  
Computer + software is a state machine as long as you restrict memory, disk space, and other types of storage (such as internet). As soon as interfacing with internet or other external hardware is allowed (implies unlimited storage), this becomes more like a Turing machine. Ever heard of a phrase 'Turing complete'? Anyhow, functional programs and obj oriented ones both end up as assembly code. I do not know Haskel (a pure functional language)/monads, but there must be an interesting relationship between that and a Turing machine. –  Job Jul 22 '11 at 3:06
    
Adding to Jobs point, any form of non-determinism also exceeds both the state machine and Turing machine models. On the internet, you have multiple non-synchronized machines, data loss through imperfect connections, etc. Even with a single-core simple computer, you have non-deterministic input from the user, but you normally ignore that issue, and pretend all the input was known in advance. –  Steve314 Jul 22 '11 at 3:33
    
@Steve314: Formally, deterministic automata are in a single state. Each input leads to a new state. For non-deterministic automata, each input can lead to multiple states. A non-deterministic automaton with N states can be emulated by a deterministic automaton with 2^N states. –  kevin cline Jun 2 at 17:49
    
@cline - In this case, you're absolutely right, but I think what I had in mind was the kind of concurrency and timing variation that happen in a real-world machine - things like a core running a bit slower because it's too hot, the exact time when the data happens to be under the read head etc. This all fits in the non-deterministic finite automata model you describe, of course, so you're absolutely correct - but the number of states will be insanely huge. I guess I might have had continuous measures such as those temperatures in mind as part of the system state too (not just consequences). –  Steve314 Jun 12 at 21:31

5 Answers 5

up vote 14 down vote accepted

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.

share|improve this answer
1  
"It is possible to model a single OOP object as finite state machine". True, but weak. It's not "possible". It's a matter of definition. A programming language's job is to express an FSM in a tidy notation. OOP is an implementation of an FSM with simpler notation for all the various states. –  S.Lott Jul 22 '11 at 11:22
1  
@S.Lott - Yes, but most people don't think of an OOP object as expressing an FSM, at least not most of the time. Using the name "state machine" tends to imply that you're using some specific implementation, such as the state design pattern or a state-ID member variable. "Modelling as a state machine" often also implies something about the specification or design documentation, distinct from the implementation of that class. Therefore, modelling a class as a finite state model subjectively means something other than just providing the source code for the class. –  Steve314 Jul 22 '11 at 11:34
    
"people don't think". True. And a deep problem. All programs are state machines. They have a lot of states. That's what the "Turing Complete" test for a programming language requires. It's a very, very strong (and absolute) rule. Rather than suggest it's "possible", it's more like "necessary" and "sufficient". –  S.Lott Jul 22 '11 at 11:37
1  
-1: Push-down automata are NOT as powerful as Turing machines. –  kevin cline Jun 2 at 17:54
1  
@kevin cline - thanks - and what was I thinking!!! Edited to strike that bit out. Despite what I said about formal study, I know better than that and should have known better back then. –  Steve314 Jun 3 at 16:15

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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer
    
"its current state" can include a great deal of information. An FSM can trivially count by having states for each number that it will count. It's finite (unlike a Turing Machine) but it's still perfectly able to count. I think you might need a better example. –  S.Lott Jul 22 '11 at 11:20
    
the sofware in your cell-phone is a collection of hideously complex state-machine which remember many data and interpret them according to the current state. –  Mawg Jan 10 '13 at 0:17

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.

share|improve this answer
    
this merely repeats points made and explained in answers posted 3 years ago, eg in this one –  gnat May 21 at 5:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.