Pushdown Automata

유한 오토마타의 경우, 입력 스트링이 왼쪽부터 오른쪽으로 소비되면서 처리되는데, 이 과정에서 앞에서 소비한 스트링의 개수를 확인할 수 없어서 앞의 스트링의 개수와 연관된 스트링이 있을 경우, 처리할 수 없습니다.

ex) CFL L = {a^nb^n | n >= 0}

 

이를 해결하기 위해 오토마타에 스택 형태의 저장 기능을 가진 오토마타가 필요하게됩니다.

 

Pushdown Automata

Automata는 입력 스트링의 왼쪽 기호부터 처리하며 Stack의 top에 변화를 일으킵니다.

그리고 각 처리 단계에서 CU(Control Unit)의 상태를 변화 시키는데, 상태는 입력 기호와 스택의 top에 의해 결정됩니다.

 

Nondeterministic Pushdown Automata (NPDA, 비결정적 Pushdown Automata)

NPDA는 다음과 같이 정의됩니다.

 

NPDA M = (Q, ∑, Γ, δ, q0, z, F)

Q = 유한개의 내부 상태

∑ = 입력 스트링의 기호

Γ = 스택 기호

δ = Q X (∑ ∪ {λ}) X Γ → Q X Γ* 의 부분집합

q0 = 초기 상태 (q0 ∈ Q)

z = 스택 시작 기호 (z ∈ Γ)

F = 최종 상태 (F ⊆ Q)

 

δ의 예시는 다음과 같습니다.

 

ex) δ(q1, a, b) = {(q2, cb), (q3, λ)} (대표적인 비결정적 선택 스택 연산 예시)

상태 q1에서 스트링 a를 소비합니다. (현재 상태에서 스택의 top은 b)

그 결과 상태 q2로 가서 스택의 top에 c를 push 하는 경우 혹은 상태 q3로 가서 스택의 top인 b가 pop된 경우가 될 수 있습니다.

 

δ(q, a, b) = (p, λ) 의 경우 스택의 pop 연산으로 스택의 top인 기호 b가 스택에서 제거됩니다.

δ(q, b, a) = (p, Ba) 의 경우 입력 기호 b를 소비하고, B를 스택에 push 합니다.

δ(q, λ, a) = (p, Aa) 의 경우 입력 기호를 소비하지 않고, 스택에 A를 push 합니다.

 

NPDA를 통해 각 상태 및 스택의 변화를 순간적 묘사를 통해 보일 수 있습니다.

 

순간적 묘사는 기호 ├를 이용하여 표기합니다.

├* 의 경우 0번 이상 전이를 한 경우이고, ├+ 는 한번 이상 전이를 한 경우입니다.

 

NPDA에 의해 승인되는 언어는 NPDA M이 최종상태에 도달하고, 입력 스트링이 모두 소모된 상태여야합니다. 이때, 스택이 비어있어야 할 필요는 없습니다.

 

CFL L에 대해서 그에 해당하는 NPDA M이 존재합니다.

즉, NPDA M에 대해 L = L(M)인 언어 L은 CFL입니다.

 

DPDA

NPDA가 존재하듯이 DPDA또한, 존재합니다. 이 경우, 결과 집합의 원소는 1개 이상 나올 수 없습니다.

(모든 q ∈ Q, a ∈ ∑ ∪ {λ}, b ∈ Γ에 대해서 δ(q, a, b)는 많아야 1개의 원소를 포함 if δ(q, λ, b) ≠ ∅ then 모든 c ∈ ∑에 대하여, δ(q, c, b) = ∅.)

 

L = L(M)인 DPDA M이 존재할 때, L은 DCFL(Deterministic Context - Free Language).

 

Finite Automata와는 달리, DPDA와 NPDA는 동등하지 않습니다.