Pushdown Automata
- 푸시다운 자동 기계(pushdown automaton, PDA)는 컴퓨터 과학에서 스택을 사용하는 자동 기계의 한 종류이다. (출처: https://ko.wikipedia.org/wiki/%ED%91%B8%EC%8B%9C%EB%8B%A4%EC%9A%B4_%EC%9E%90%EB%8F%99_%EA%B8%B0%EA%B3%84)
- PDA= Finite State Machine + A Stack (Push+Pop)
- A pushdown Automata has 3 components
- An input tape
- A Finite Control Unit
- A stack with infinite size
Pushdown Automata의 구성
- 푸시다운 오토마타는 다음과 같은 7가지의 요소로 구성
M = (Q, Σ, Γ, δ, q0, Z, F)
Q : 상태들의 유한 집합
Σ : 입력 알파벳의 유한 집합
Γ : 스택 알파벳의 유한 집합
δ : 전이함수, Q×(Σ∪{λ})×Γ→Q×Γ*의 부분집합
q0∈Q : 초기상태
Z∈Γ : 스택시작심
F⊆Q : 최종상태들의 집합
- λ(람다)기호: 입력 없음
Pushdown Automata 설계
- 현재의 input symbol / 스택의 top symbol에 따라 다음 행동을 결정.
- a가 들어오면 스택 탑에 있는 b를 c로 변경 / 상태를 q1에서 q2로 전이
- a는 대다수가 엡실론.
- b는 스택 탑에 존재하고 popped 됨.
- c는 스택에 pushed 됨.
공부방