푸시다운 오토마타 ( Push-Down Automata )

푸시다운 오토마타의 7개 구성요소

M=(Q, Σ, T, δ, q0, z0, F)
  Q : 상태들의 유한집합
  Σ : 입력기호들의 유한집합
  T : 스택기호들의 유한집합
  δ : 전이함수 Q X (∑∪{ε}) X T -> Q X T*
  q0 ∈ Q : 시작(start state)상태
  z0 ∈ T: 스택의 시작기호
  F ⊆ Q : 종결상태(final state)의 집합

전이함수δ (q,a,z) = {(p1,r1),(p2,r2),...,(pm,rm)}에서
- m = 1 이면 결정적 푸시다운 오토마타(DPDA:Deterministic Push-Down Automata)
- m ≥ 2 이면 비결정적 푸시다운 오토마타(NPDA:Non-Deterministic Push-Down Automata)