An uninitiated reader who wishes to use this paper for insight into the correspondence between program graphs and automata might first consult the chapter on star height in the book by Salomaa [1]. It would also be useful to review the paper by Kosaraju [2] concerning the operations exit(i) to exit i embedded loops and halt.

Basically, star height is the minimum number of embedded starred subexpressions necessary to represent the regular expression for a language. Cohen’s result [3] states that the rank of a state diagram is equal to the regular expression star height for a qualified class of languages. This paper examines cases in which halt can be exchanged with exit(i) and vice versa. The application of Cohen’s result is that the effect on the star height of the underlying automaton is used as the proof vehicle. This is in contrast to examining program structures explicitly. While not the main result, one interesting conclusion is that a program containing only exit(1) cannot always be converted to one containing only halt and vice versa.