The intuitive sense of a “deterministic” acceptor isthat there is exactly one run for each input sequenceand the outcome of this run uniquely determinesacceptance or rejection. This is imperfectly achievedfor the PDA model.
Definition 5.3.1: a PDA M = (S, _______, s0, Z, R) is a deterministic PDA (DPDA) provided that
(i) for each s_S and X__, if _(s, _, X) = _, then _(s, _, X) has exactly one element for each ___,
(ii) for each s_S and X__, if _(s, _, X) ° _, then _(s, _, X) has exactly one element and _(s, _, X) = _ for all ___, and
(iii) for s_S and a_____{_}, if _(s, a, Z) ° _, then _(s, a, Z) = {(t, _Z)} for some t_S and ___*.
Previous slide | Next slide | Back to first slide | View graphic version |