Reading the book Practical Foundations for Programming Language.

In section 5.1 Transition Systems, the author said that

Whereas all final states are, by convention, stuck, there may be stuck states in a transition system that are not final.

Thus every complete transition sequence is maximal, but maximal sequences are not necessarily complete.

It seems that in practice a stuck state is always final, but I wonder when is a stuck state not final? (Could you give me an example?)

Also, if we think that the stuck state is always final, it seems no different between maximal and complete?

A transition sequence is maximal iff there is no $s$ such that $s_n \mapsto s$, and it is complete iff it is maximal and, in addition, $s_n$ final.

Also, do the states mentioned here refer to different states? If there is a fixed-point state in a transition system, the state is final or stuck?


  • $\begingroup$ @JohnL. I am sorry for no further feedback on this issue (I forgot indeed...). Because later I seemed to have a better answer. A "final" state is something like final state in finite automata. They are marked by the creator of that system, whereas a "stuck" states is the state satisfy the "stuck" condition. So "final" state is included in "stuck" state. Nevertheless, your answer still gave me a lot of inspiration, thanks! (I have upvoted it.) $\endgroup$
    – chansey
    Dec 22, 2021 at 9:01

1 Answer 1


In practice, a "final" state usually represents the state when the running of a program in a certain programming language is returning a value. (Nothing is considered as a value as well.) No more instruction can be carried out.

In contrast, a "stuck" state can also represents the state when the running of a program got stuck (in the usual sense of English) when there is no instruction can be done further. For example, when a program is assigning a string to a variable that can only hold a number. There is nothing further that can be done by the program, since "no transition is possible", assuming nothing like some exception mechanism to deal with that kind of "illegal" situations is available.

One central purpose of designing a programming Language and writing a compiler/interpreter is to ensure the running of a program will never got into a "stuck" state except when it returns.

"If there is a fixed-point state in a transition system, the state is final or stuck?" If defined as final, that state is final (and stuck). Otherwise, it is neither final nor stuck.

  • $\begingroup$ A program that runs to a "stuck" state that is not "final" will be represented by a transition sequence that is maximal but not complete. $\endgroup$
    – John L.
    Nov 19, 2021 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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