[Automata] Pushdown Automata

Chapter 7의 내용이다!

 

일단 Pushdown Automata와 그 전의 automata와 가장 크게 다른 점은

pushdown automata는 스택을 사용할 수 있다는 것이다!

 

Nondeterministic Pushdown Automata

Pushdown Automata의 정의

 

M = (Q, Σ, Γ, 𝛿, q_0, z, F)

* Γ 은 감마라고 부른다. 

 

잘 보면 기존에 배웠던 finite automata에서 2가지의 원소가 추가되었다. 

바로 Γ 와 z이다.

 

Q: control unit의 initernal state의 유한 집합Σ: input alphabet

 

Γ: 유한한 개수의 집합인 stack alphabet

𝛿: Q X ( Σ sum {ƛ}) X Γ : transifion function이 Q X Γ* 의 유한 집합이다. 

q_0: Q에 속하는, control unit의 initial state

z: Γ 에 속하는, 스택의 start symbolll

F: Q의 부분집합인, final state의 집합

 

예시로 알아보자!

Q = {q_0, q_1, q_2, q_3}

Σ = {a, b}

Γ  = {0, 1}

z = 0

F = {q_3}

이고 initial state가 q_0이라고 해 보자.

 

𝛿(q_0, a, 0) = {(q_1, 10), (q_3, ƛ)}

...

 

 

Pushdown Automata와 CFG

 

Deterministic Pushdown Automata와 Deterministic CFG