Strict interpretations of deterministic pushdown acceptors

Three results are established. The first is that every nondeterministic strict interpretation of a deterministic pushdown acceptor (dpda) has an equivalent, deterministic, strict interpretation. The second is that ifM₁ andM₂ are two compatible strict interpretations of the dpdaM, then there exist deterministic strict interpretationsM andM such thatL(M) =L(M₁)L(M₂) andL(M) =L(M₁)L(M₂). The third states that there is no dpda whose strict interpretations yield all the deterministic context-free languages.This author was supported in part by the National Science Foundation under Grant MCS-77-22323.