next up previous
Next: About this document Up: No Title Previous: Nondeterministic FSA (NFSA)

Finite Executions and Infinite Behavior

Recall the red and blue light example where the behavior of the light is infinite because there are an infinite number of traces associated with the light. Also, some of those traces are infinite (e.g., pressing red forever).

In some models of state machines, in particular, Communicating Sequential Processes (CSP), which we will be covering in detail later this term, infinite traces are not included in the machine's behavior. This kind of model is sometimes called the finite-trace model. The behavior of the machine is defined to be a possibly infinite set of finite traces.

Why is this a reasonable model? It has a simple structure which has some nice mathematical properties. Using this model may help simplify your thinking about the system; you know every trace in the behavior is finite so you don't have to worry about infinite traces. With a model that has both finite and infinite traces, whenever you prove some property about the behavior it describes, you usually have to structure your proof into two parts, one to handle the finite trace case and one to handle the infinite trace case. But perhaps the most compelling intuitive argument for this model is that you can never see an infinite execution; if you can't observe this behavior then why should we model it?

What are some of the disadvantages of this model? Because we cannot talk about infinite traces, the biggest disadvantage is that we cannot talk about certain properties like deadlock and fairness. To do so requires adding a lot of complicated structure to either traces or behaviors of a state machine.

We won't dwell on the advantages and disadvantages of this model here since we'll see more of it later.



Norman Papernick
Mon Mar 18 15:31:49 EST 1996