Nondeterminism

Talking about finite automata, we should remember these strange things called nondeterministic finite automata (NFA). What is an NFA, anyway?

The NFA is most important in the area of syntax analysis and computability. It describes a finite automata which is - in principle - able to follow all paths, if required, in parallel, accoring to its input data and the definition of the transitions.

Sometimes, people interpret it as finding just the right way through the transition system, just like magic. If there is a way through the graph which represents the sequence of input data, the system will just walk this way and end in a final state. But we know that computers do not work this way, at least not yet. Quantum computers seem to have some similarity to these NFAs.

That is, it's a matter of theoretical computer science, isn't it?

Not quite. It is again a matter of interpretation.

Agents and NFAs

Our intention is to find a proper description of the agent's behavior. On the other hand, we stressed the autonomy of the agent several times. From outside, the agent sometimes takes decisions that cannot be explained according to the incoming messages.

Similar to NFAs used for grammars, the transition system shows which way the agent can react, given some sequence of input data. But unlike those NFAs, the agent need not automatically choose the right way. It changes state according to previous messages or to other non-obvious reasons, and after this transition, another set of messages may be accepted.

Note the different situation:

• You may select some sequence of input data for an NFA, and using its transition table, you can find out which transitions the system must trigger to accept these data.
• For agents, you know which data is acceptable at this state, and using the transition table, you can deduce which input data will be accepted after the transition. If there are several matching transitions, you need to take into account all possible target states.

Pseudo nondeterminism

The following figure shows a transition system which contains nondeterminism.

Nondeterministic transition system

Starting from the left state, the agent waits for a message of type A. Unfortunately, the agent may take two different ways: Following the upper path, the agent would answer with a reply message of type B; it would be of type C if the agent had followed the lower path.

If we ignored the output data, this would have to be called nondeterminism, no doubt. But we do have output here. We call the exchange of input data, together with the output data, a interaction. Interactions are determined by their input and output data. Thus, we do not have true nondeterminism here: There is at least some external instance - the receiver - which can distinguish between the two possible state changes of this agent. It will not have any problem to decide how to continue with the communication because the return data will trigger different transitions in the commmunication partner.

Therefore, we add another pair of transitions starting in the upper middle state. Now the interactions are the same. This is an example of true nondeterminism: We cannot directly tell which path was followed by the agent, and neither does the receiver.

For true nondeterminism, all possible result states need to be taken in consideration. It cannot be deduced which state the agent is actually in until it triggers another transition.

We call the nondeterminism with different interactions pseudo nondeterminism.