Pushdown Automata

oak_cassia·2022년 5월 25일
0

Compiler

목록 보기
4/9

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

  • QQ:states 집합

  • Σ\Sigma: input symbols

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

  • q0q_0: start state

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

  • FF: final state

  • δ\delta: transition function

    • δ:Q×Σ×ΓQ×Γ\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 보다 표현력이 좁다
profile
벽에 붙은 달팽이 ↑i@

0개의 댓글