푸시다운 오토마타

푸시다운 오토마타는 7개의 요소로 구성

M = (Q, Σ, T, δ, q0, z0, F )

Q : 상태들의 유한 집합

Σ : 입력 기호들의 유한 집합

T : 스택 기호들의 유한 집합

q0 ∈ Q : 시작 상태

z0 ∈ T : 스택의 시작 기호

F ⊆ Q : 종결 상태의 집합

δ : 사상함수 Q x ( Σ ∪ { ε } ) x T -> Q x T*

 

δ(q, a, z) = { (p, r) }이라 하면

- q의 상태에서 입력기호 a를 받았을 때 스택의 톱에 z가 있다면 상태는 p로 이전

- 스택의 톱 z는 스택에서 삭제, 스택에는 r이 푸시

- 만약 r이 ε이면 스택에서 삭제만

 

δ(q, a, z) = { (p1, r1), (p2, r2), ... (pm, rm) }일 때

- 상태는 pi(i = 1, .. m)으로 전이, 스택 탑 z는 삭제, 스택에는 ri 삽입

- 이때 입력 제어는 한 자리 오른쪽으로 이동

- m = 1이면 결정적 푸시다운 오토마타 (deterministic push-down automata)

- m >=2이면 비결정적 푸시다운 오토마타 (non-deterministic ~ )

 

유한 오토마타의 입력 문자열 인식

- 입력 문자열을 모두 읽은 후 마지막 상태가 종결 상태냐 아니냐

 

푸시다운 오토마타에서의 입력 문자열 인식

- 유한 오토마타의 경우처럼 종결 상태에 의해서 인식하는 방법

    - L(M) = { w | (q0, w, z0) => (p, ε, r), p ∈ F, r ∈ T* }

- 비어있는 스택에 의해 인식하는 방법

    - N(M) = { w | (q0, w, z0) => (p, ε, ε), p ∈ Q }

    - 푸시다운 오토마타는 입력 문자열을 모두 읽은 후에도 이동이 일어남

    - 스택이 비어있는 경우에는 이동이 일어나지 않음

 

예시

L = { 0^n1^n | n >= 1 }을 인식하는 PDA M과 같을 때 0010과 0101이 인식되는가?

M = { {q0, q1, q2}, {0, 1}, {z, 0}, δ, q0, z, {q0} }

δ :

δ(q0, 0, z) = { (q1, 0z) }

δ(q1, 0, z) = { (q1, 00) }

δ(q1, 1, z) = { (q2, ε) }

δ(q2, 1, z) = { (q2, ε) }

δ(q2, ε, z) = { (q0, ε) }

 

0011 인식 과정

(q0, 0, z)

=> (q1, 0, 0z)

=> (q1, 1, 00z)

=> (q2, 1, 0z)

=> (q2, ε, z)

=> (q0, ε, ε)

비어있는 스택에 의해 인식되는 DPDA이자,

q0가 종결상태니 종결상태에 의해서 인식되는 DPDA

 

0101은?

δ(q0, 0, z)

=> δ(q1, 1, 0z)

=> δ(q2, 0, z)     여기서 진행 불가

0101은 인식되지 않음

 

푸시다운 오토마타의 확장 (한번에 한 글자 -> 문자열)

δ : Q x ( Σ ∪ { ε } ) x T -> Q x T* 에서

δ : Q x ( Σ ∪ { ε } )* x T -> Q x T* 로 확장

 

0011 인식 과정을..

δ(q0, 0011, z)

=> δ(q1, 011, 0z)

=> δ(q2, 11, 00z)

=> δ(q2, 1, 0z)

=> δ(q2, ε, z)

=> δ(q0, ε, ε)