Finite State Machines (FSMs) are what I like to refer to as 'fake AI'. FSMs are basically preprogrammed scenes. You should see them as a flowchart. For example, imagine the following chat flowchart:

This is a very simple FSM. What a program does is simply list a number of options to reply to a question. Based on the answer two the first question, you will be presented with a new list of choices.

FSMs are bascially large trees of options. When the tree of options is large enough, the AI, or often character, can be quite realistic.

FSMs have some obvious pros and cons. As they are very straightforward, with the right software, they are easy to make, implement and manage. Also, because they are predefined, they require little processor power. If one was to implement a neural network for each character, game sizes would be humungous and would require a supercomputer to be played.

Their simplicity can of course also be a downside. Behaviour of characters is often predictable when the FSM tree isn't large enough. However, for most applications this is not a big problem. A random factor can be included to prevent this.

As you might have imagined, FSMs can also be used for other applications than chatting. In the popular game Quake, FSMs are used for controlling the behaviour of many items in the game, including weapons. They can make a complex environment very easy to manage, because it is 'split up' into different items which are then taken care off individually.

The following URL has more information on FSMs, including code examples.

http://www.microconsultants.com/tips/fsm/fsmarticl.pdf (Broken?)