Wednesday, May 23, 2007

Deterministic Push down Automata (DPDA)

“Deterministic Push down Automata” (DPDA):

Formal definition:
A PDA M can be defined as a 7-tuple:
M = (Q,Σ,Γ,q0,Z0,A,δ) where
 Q is a finite set of states
 Σ is a finite set of the input alphabet
 Γ is a finite set of the stack alphabet
 q0 is the start state, an element of Q
 Z0 is the initial stack symbol, an element of Γ
 A is the set of final states, a subset of Q
 δ is a finite transition relation (Q x (Σ U {Λ} x Γ ) ----> the set of finite subsets of (Q x Γ* )

No comments: