Nondeterminism is considered to be ignorance about the actual state transition sequence performed during a computation. The number of distinct potential paths from state i to j forms a matrix [nij]. The behavior of a nondeterministic program is defined to be this multiplicity matrix of the state transitions. The standard programming constructs have behaviors defined in terms of the behaviors of their constituents using matrix addition and multiplication only. The spectral radius of the matrix assigned to an iterating component characterizes its convergence. The spectral radius is shown to be either 0 or else ⩾ 1. The program converges iff the spectral radius is zero, diverges deterministically iff the spectral radius is one, and has a proper nondeterministic divergence iff the spectral radius exceeds one. If the machine has an infinite number of states the characterization of convergence is given graph theoretically. The spectral radii of synchronous and interleaved parallel noncommunicating systems are easily computed in terms of the spectral radii of the components.

The normal form grammars, such as those developed by Chomsky and Greibach, preserve certain properties of the original grammar. Ordinarily attention is only directed to weak equivalence, that is, that the original grammar and its normal form version both generate the same language. By paying greater attention to the functions carrying a grammar to its normal form, considerably stronger preservation properties can be proved. We demonstrate that several normal forms preserve ambiguities. More surprisingly, a variant of Chomsky’s normal form, called canonical two form, forms an adjunction in connection with the original grammar. This fact shows that canonical two form preserves a large number of the structural properties of the original grammar. In particular, we show that the canonical two form is $LR(k)$ if the original grammar is $LR(k)$, strengthening a result of Gray and Harrison. Preservation of structural properties such as ambiguity is important in semantic considerations, and the methods given for the determination of property preservation seem to be of general applicability.