푸시다운 오토마타 PDA

Intro

• 푸시다운 오토마타(Push-Down Automata)에 대하여 알아보기

푸시다운 오토마타 PDA

푸시다운 오토마타는 인식기의 한 종류로 유한 상태제어

입력 테이프, 스택으로 구성되어 있다.

입력 테이프는 입력 스트링을 유지하고 있으며

스택은 보조 기억장치로 푸시다운 리스트 라고 부른다.

유한 상태 제어는 전체의 행동을 제어하며

현재 입력심벌과 스택의 top에 따라 행동한다.

푸시다운 오토마타

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

푸시다운 오토마타 P는 7개의 요소를 가진다.

P = ( Q , ∑ , Γ , δ , q₀ , Z₀ , F)

Q : 상태들의 유한 집합

∑ : 입력 심벌의 유한 집합

Γ : 스택 심벌의 유한 집합

δ : 사상 함수 Q × (∑ ∪ {ε}) × Γ -> Q × Γ^*

q₀∈Q : 시작 상태

Z₀∈Γ : 스택의 시작 심벌

F⊆Q : 종결 상태들의 집합

PDA P의 형태

현재 상태를 나타내는 PDA P의 형태는

Q×∑^*×Γ^*의 트리플 (q, ω, a)로 나타낸다.

q는 현재의 상태이며, ω는 읽지 않은 입력 부분, a는 스택의 내용을 나타낸다.

ω = ε 인 경우는 모든 입력 심벌이 읽혀졌음을 의미하고,

a의 왼쪽 첫 번째 심벌이 스택 top에 있는 심벌에 해당된다.

예제

어떤 한 시점에서 P의 형태가 (q_i, a_ia_i+1…a_n, Z_iZ_i+1…Z_i+k) 일 때,

현재 상태는 q_i이고 아직 읽지 않은 부분 즉, 앞으로 봐야할 스트링이 a_ia_i+1…a_n이다.

여기서 a_i가 현재 보고있는 입력 심벌이다.

또한, 스택의 내용은 Z_iZ_i+1…Z_i+k가 되며 Z_i가 스택 top 심벌이다.

PDA의 이동

P에 의해 한 상태에서 다른 상태로의 이동은 ├ 로 표기한다.

만약 a = ε 인 경우, ε-이동 이라고 하는데, 현재의 입력 심벌에 대해서는 고려되지 않고 입력헤드도 움직이지 않는다. 그러나 유한 제어 상태가 변하고 스택의 내용도 바뀐다.

ε-이동은 모든 입력 심벌이 읽혀졌을 때에도 발생 할 수 있다.

그러나 스택이 비었을 경우에는 어떠한 이동도 가능하지 않다.

시작 상태에서 입력스트링 ω를 다 본 상태가 종결 상태에 속하면

스트링 ω는 P에 의해 인식된다고 말한다.

예제

PDA P({q₀, q₁, q₂},{0 1}, {Z, 0}, δ, q₀, Z, {q₀} )는 스트링 0011, 0001을 인식 하는가?

①δ(q₀, 0, Z) = {(q₁, 0 Z)}

②δ(q1₁, 0 , 0) = {(q₁, 00)}

③δ(q₁, 1, 0) = {(q₂, ε)}

④δ(q₂, 1, 0) = {(q₂, ε)}

⑤δ(q₂, ε, Z) = {(q₀, ε)}

(1) (q₀, 0011, Z)

├ (q₁, 011, 0Z)

├ (q₁, 11, 00Z)

├ (q₂, 1, 0Z)

├ (q_{2, ε, Z)}

├ (q₀, ε, ε)

∴ 0011을 다 본 상태인 q₀이 종결 상태이기 때문에 인식된다.

(2) (q₀, 0001, Z)

├ (q₁, 001, 0Z)

├ (q₁, 01, 00Z)

├ (q₁, 1, 000Z)

├ (q₂, ε, 00Z)

∴ 0001을 다 본 상태인 q₂가 종결 상태가 아니기 때문에 인식되지 않는다.

Context-free 언어와 PDA언어

지금까지의 내용을 바탕으로 CFG가 주어졌을 때, 그에 해당하는 PDA를 구성할 수 있고

역으로 PDA가 주어졌을 때, PDA가 인식하는 언어와 같은 언어를 생성하는 CFG를 만들 수 있다.

예제

다음 문법 G가 주어졌을 때, L(G)를 인식하는 PDA P를 구성해 보자.

E -> E + T | T
T -> T * F | F
F -> (E) | a

먼저, P=({q}, {a, +, *, (,)}, {E, T, F, a, +, *, (,)}, δ, q, E, φ) 이다.

그리고 δ 함수는 다음과 같이 정의된다.

①δ(q, ε, E) = {(q, E+T), (q, T)}

②δ(q, ε, T) = {(q, T*f), (q, F)}

③δ(q, ε, F) = {(q (E)), (q,a)}

④δ(q, x, x) = {(q, ε), 여기서 x∈{a, +, *, (, )}}

입력 a+a*a에 대하여 P는 다음과 같은 이동을 할 수 있다.

(q, a+a*a, E)

├ (q, a+a*a, E+T)

├ (q, a+a*a, T+T)

├ (q, a+a*a, F+T)

├ (q, a+a*a, a+T)

├ (q, +a*a, +T)

├ (q, a*a, T)

├ (q, a*a, T *F)

├ (q, a*a, F *F)

├ (q, a*a, a *F)

├ (q, *a, *F)

├ (q, a, F)

├ (q, a, a)

├ (q, ε, ε)

E로부터 a+a*a의 좌측 유도에 대응되게 규칙을 적용 한 것과 같다. 시작 심벌로부터 아래로 내려가면서 스트링을 생성하기 때문에 이러한 방법을 top-down 구문 분석 방법이라 한다.

CFG에서 우측 유도를 역으로 적용함으로써 bottom-up 파서로 작동하는 확장된 PDA를 만들 수 있다.

참고 저서

오세만, 컴파일러 입문, 정익사,2010, 208쪽