摘要: In computations on push-down store machines, the following three types of constraints are of greater interest: 1) determh~ acy; 2) computability in real time; 3) computation with emptying of the store. Instead of the third type of constraint, it is more convenient to consider a more general cases ie, the number of generalized terminal states is finite. It is not difficult to extend the results to the case of an empty store. The above three types of constraints yield eight distinct combinations. To each of these eight distinct cases there corresponds a certain class of languages. In this note we shall establish the mutual position of these classes. If determinacy is not required, it is well known that the constraints 2 or 3 have no effect on membership in the class of all CF languages [1, 2]. Therefore our main interest will be devoted to deterministic CF languages.
springer.com参考文章(0)