Pushdown Automata

푸시마타 오토마타는 CFG를 인식하기 위한 오토마타

• $Q$:states 집합

• $\Sigma$: input symbols

• $\Gamma$: 스택에 저장되는 심볼

• $q_0$: start state

• $Z_0$: 스택의 start 심볼, 라지 감마에 포함

• $F$: final state

• $\delta$: transition function

  • $\delta: Q \times \Sigma \times \Gamma \rightarrow Q \times \Gamma$
  • 스택의 상태조건이 더 생긴다고 보면 된다.
  • 오토마타를 그릴 때 ( a, X / Y)
  • 순서대로 input, current stack top, stack top replacement

인식

• final state에서 입력이 더 이상 없으면 인식
• empty stack일 때 입력이 더 이상 없으면 인식

DPDA

• Deterministic PDA
• $\delta$ 가 하나의 멤버만 갖는다. input에 $\epsilon$ 포함
• state와 stack의 top에 대해 알파벳 중 하나의 input이 있으면 엡실론은 없다.
• Finite automata 에서와 달리 NPDA 보다 표현력이 좁다