Deterministic
PDA (DPDA)
Gist:
Deterministic PDA makes no more than one move
from any
configuration.
Definition: Let M = (Q, S, G, R, s, S, F) be a PDA. M is a deterministic PDA if for each rule
Apa ® wq Î R, it holds that R – {Apa ® wq} contains no rule with the left-hand side equal to Apa or Ap.
Illustration:
Configuration:
a
p
A
y
x
Ap
®
w1q1
Apa ® w2q2
No more that one rule of the forms
32/50