Extended PDA (EPDA)
Gist:
The pushdown top of an EPDA represents a string rather than a single
symbol.
Definition: An Extended
Pushdown automaton (EPDA) is a 7-tuple M = (Q, S, G, R, s, S, F),
where Q, S, G, s, S, F are defined as in an PDA and R is a finite set of rules of the form: vpa ® wq, where v, w Î G*, p, q Î Q, a Î S È {e}
Illustration:
Pushdown of PDA:
Pushdown of EPDA:
A
x
x
v
PDA
has a single symbols as the pushdown top
EPDA
has a string as the pushdown top
34/50