SYNTHESIS OF A NONDETERMINISTIC AUTOMATON FROM ITS LOGICAL SPECIFICATION .2.

In Part I [1] we described an algorithm to construct the reduced form of the automaton A(F(t)) specified by the formula vr F(t) where the ra nk of the formula F(t) does not exceed 1. Part II considers two algori thms that construct an automaton with a number of states close to the reduced form of the automaton A(F(t)) for the case of arbitrary formul as F(t) allowed by the specification language. Both algorithms rely on the same idea of decomposing the formula F(t) as the algorithm of [1] , but examination of formulas of a more general kind required a substa ntial refinement of the decomposition idea, leading to two different a lgorithms. The last section of the article demonstrates how the algori thm of [1] can be applied in the general case after transforming the g iven formula to a formula of rank 1. The concepts and notation that ar e given without definition correspond to their usage in [1].