강의 4

푸시다운 오토마타와 CFG ↔ PDA

유한 오토마타에 스택 한 개를 끼워 넣으면, 어디까지 갈 수 있을까?

1. 스택 한 개의 차이

지난 강의에서 우리는 문맥 자유 문법(CFG)을 익혔다. 이번에는 그 문법이 만들어 내는 언어를 기계로 받아들이는 장치를 짚어 본다. 결정적 유한 오토마타(DFA)는 기억 용량이 정확히 상태 개수만큼이라, aⁿbⁿ처럼 a의 개수를 b가 다 끝날 때까지 들고 있어야 하는 문제 앞에서 무력했다. 해법은 의외로 소박하다. 카페에서 접시를 쌓아 올리듯, 오토마타 옆에 무한 스택 하나를 두는 것이다.

이 장치를 푸시다운 오토마타(pushdown automaton, PDA)라 부른다. 입력을 한 글자씩 읽으면서 스택의 맨 위(top)를 보고, 거기에 무엇을 새로 쌓을지(push) 혹은 무엇을 걷어 낼지(pop)를 결정한다. 흥미로운 점은 PDA는 본디 비결정적(nondeterministic)이라는 사실이다. 결정적 모델은 표현력을 잃기에, 처음부터 분기를 허용한다.

정의 (PDA). 푸시다운 오토마타는 6-튜플 ⟨Q, Σ, Γ, δ, q0, F⟩ 이다. 여기서
  • Q는 유한 상태 집합,
  • Σ는 입력 알파벳, Γ는 스택 알파벳(서로 같을 필요 없음),
  • q0 ∈ Q는 시작 상태, F ⊆ Q는 수락 상태 집합,
  • 전이 함수 δ : Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → ℘(Q × (Γ ∪ {ε})) 는 (현재 상태, 읽을 입력 글자 또는 ε, 스택 top에서 꺼낼 기호 또는 ε)을 받아 (다음 상태, 스택에 새로 쌓을 기호 또는 ε)들의 유한 집합을 돌려준다.
입력을 모두 소비하고 어떤 수락 상태에 있을 수 있으면 PDA는 그 입력을 수락한다.

전이 함수가 ε을 세 자리 모두에 허용한다는 점에 주목하자. 입력을 안 읽고도 움직일 수 있고, 스택을 안 건드려도 되고, 스택에 안 쌓아도 된다. 이 자유도가 비결정적 분기를 빚어낸다.

한 줄 메모. 어떤 교과서는 한 번에 여러 기호를 푸시할 수 있게 정의하지만, 일반성에는 차이가 없다. 한 번에 한 글자씩 ε-전이로 나누어 쌓으면 그만이기 때문이다.

2. 첫 예제: { aⁿbⁿ : n ≥ 0 }

고전 중의 고전. 아이디어는 단순하다. a를 읽을 때마다 스택에 표식 A를 쌓고, b가 시작되면 a 하나마다 A를 하나씩 걷어 낸다. 입력 끝에서 스택이 처음 상태로 돌아와 있으면 a와 b의 개수가 같다.

구현 디테일 하나. 스택이 비었는지 검사하는 표준 트릭은, 시작과 동시에 바닥 표시 $를 깔아 두는 것이다. 그러면 "스택이 비었음"을 직접 묻는 대신 "$가 top에 있음"을 물으면 된다.

상태:    qstart --(ε, ε → $)--> q1
         q1     --(a, ε → A)--> q1          (a를 읽고 A 푸시)
         q1     --(ε, ε → ε)--> q2          (b 단계로 비결정적 전환)
         q2     --(b, A → ε)--> q2          (b를 읽고 A 팝)
         q2     --(ε, $ → ε)--> qaccept     (바닥이 보이면 수락)

입력 a a a b b b 의 진행:
  스택        남은 입력
  $           a a a b b b
  A $         a a b b b
  A A $       a b b b
  A A A $     b b b
  A A A $     b b b      ← q1 → q2 ε-전이 (분기)
  A A $       b b
  A $         b
  $           ε
  ε           ε          ← 수락

"q1에서 언제 q2로 넘어가야 하는가"라는 결정은 비결정성에 맡긴다. 어떤 분기든 입력 끝에서 수락할 수 있는 길이 하나라도 있으면 PDA는 그 문자열을 받아들인다.

예제 (균형 괄호). Σ = { (, ) } 위에서 균형 잡힌 괄호 언어 또한 같은 기법으로 인식된다. 여는 괄호는 스택에 푸시, 닫는 괄호는 top의 여는 괄호와 짝이 맞으면 팝. 입력 끝에서 바닥 $만 남아 있으면 수락이다. 중첩된 (())와 나란히 놓인 ()()을 같은 자료구조 위에서 자연스레 다루는 점이 핵심이다.

3. CFG → PDA: 유도를 스택 위에서 시뮬레이션

이제 큰 정리로 향하는 한 방향, "CFG가 만든 언어는 어떤 PDA가 인식한다"를 보자. 발상은 깔끔하다. 스택을 유도의 작업대로 쓴다. 좌측 유도(leftmost derivation)는 항상 "맨 왼쪽 비단말을 한 번 펼친다". 그러므로 스택 top에 비단말이 있으면 그것을 규칙의 우변으로 바꿔 치우면 된다.

정리. 모든 문맥 자유 문법 G에 대해 L(G)를 인식하는 PDA M이 존재한다.
증명 스케치. G = ⟨V, Σ, R, S⟩가 주어졌다고 하자. 세 상태 qstart, qloop, qaccept 만으로 충분하다.
  1. qstart에서 ε-전이로 시작 변수 S를 푸시하고(아래에 바닥 표시 $도 함께) qloop으로 간다.
  2. qloop에서 두 종류의 동작을 비결정적으로 고른다.
    • 확장: top이 비단말 A이면, 어떤 규칙 A → α를 골라 A를 팝한 뒤 α를 (역순으로) 푸시한다. 그래야 α의 첫 글자가 다시 top에 오기 때문이다.
    • 대조: top이 단말 a이고 다음 입력 글자가 a이면, 입력 a를 읽고 a를 팝한다. 글자가 어긋나면 그 분기는 죽는다.
  3. 입력을 다 읽고 스택 top이 $이면 qaccept로 ε-전이.
어떤 입력 w가 G에서 좌측 유도되면, 위 PDA의 비결정적 분기 가운데 정확히 그 유도를 따라가는 분기가 존재하고, 그 분기는 w를 수락한다. 역도 마찬가지로, 수락하는 실행은 좌측 유도를 추출해 낸다.

한 번에 여러 기호를 푸시한다는 표현은 앞서 언급한 대로 ε-전이 연쇄로 풀어 쓰면 된다. 스택을 "역순으로" 쌓아야 한다는 점이 학생들이 자주 놓치는 자리다. α = X1X2X3이라면 X3을 먼저, 그 위에 X2, 그 위에 X1을 쌓아야 X1이 top에 온다.

4. PDA → CFG: Apq 비단말로 구간 분해

역방향은 한 차례 정신을 단단히 차려야 한다. 임의의 PDA가 인식하는 언어를 어떻게 문법으로 환원할 수 있을까? 그 핵심 발상은 다음과 같다.

PDA의 동작에서 한 토막을 떼어 보자. 시점 A에서 상태 p에 있고 스택의 어떤 기호 X가 top이며, 시점 B에서 상태 q에 있고 그 X가 마침내 팝되어 사라지는 순간이라고 하자. 그 사이 스택은 X를 일단 떠받친 채 위로 더 쌓였다 다시 무너져 내렸을 것이다. 즉, 시작과 끝 사이의 스택 높이는 X 위로만 변동했다. 이 구간 동안 PDA가 읽은 입력을 한 비단말 Apq로 부르자.

일반성을 위해 PDA를 약간 표준화한다. (i) 유일한 수락 상태가 하나이고, (ii) 수락은 스택이 비었을 때만 일어나며, (iii) 모든 전이는 푸시 또는 팝 가운데 정확히 하나만 한다. 이렇게 정리하면, 임의의 수락 실행은 "처음에 무언가를 푸시 — 그 위에서 사다리꼴이 오르내림 — 결국 그것을 팝"의 형태로 분해된다.

정리. 모든 PDA가 인식하는 언어는 어떤 CFG가 생성한다.
증명 스케치. 표준화된 PDA의 각 상태 쌍 (p, q)마다 비단말 Apq를 둔다. 의도된 의미: Apq가 유도하는 문자열 = 상태 p에서 스택이 어떤 높이일 때 시작해, 상태 q에서 정확히 그 높이로 돌아오는 동안 PDA가 읽을 수 있는 입력. 시작 변수는 Aq0qaccept로 잡는다.

규칙은 두 종류로 나온다.

  • 케이스 1 — 스택을 비웠다 다시 채우는 경우. 구간 (p, q)가 중간 시점 r에서 한 번 같은 스택 높이로 돌아왔다고 하자. 그러면 (p, r) 구간과 (r, q) 구간으로 잘린다. 이를 규칙 Apq → Apr Arq 로 모든 r ∈ Q에 대해 추가한다.
  • 케이스 2 — 처음 푸시가 끝까지 함께 가는 경우. 구간이 시작에 푸시한 기호가 마지막 한 번에야 팝되는 형태일 때다. 즉 첫 전이가 (p, a, ε) → (r, X)로 X를 푸시하고, 마지막 전이가 (s, b, X) → (q, ε)로 그 X를 팝한다고 하자. 그 사이 (r, s) 구간은 X 위에서만 놀았으므로 스택 X를 보지 않는 PDA의 한 동작과 같다. 따라서 규칙 Apq → a · Ars · b 를 가능한 모든 (a, b, X, r, s)에 대해 추가한다. (a 또는 b는 ε일 수 있다.)
  • 마지막으로, 자명한 빈 구간을 위해 모든 p에 대해 App → ε.
이 문법이 PDA의 수락 실행을 정확히 흉내 낸다는 사실은 실행 길이에 대한 귀납으로 보인다. 짧은 구간(0-스텝)이 ε에 대응하고, 긴 구간은 두 케이스 가운데 하나로 반드시 분해된다는 점이 핵심이다.

증명은 길어 보여도 분해 원리는 한 문장이다. 스택은 결국 자기가 쌓은 것을 자기가 다 치우고 가야 한다. 그 "쌓고 치움"의 기록을 비단말 Apq가 저장하는 것이다.

5. 동치성 정리와 결정적 PDA

정리 (CFL ↔ PDA). 언어 L이 문맥 자유 언어인 것은 어떤 PDA가 L을 인식하는 것과 동치다.

두 방향의 구성을 합치면 위 정리가 된다. 이제 우리는 같은 사물을 두 가지 언어로 말할 수 있다. 문법으로 묘사하거나, 기계로 묘사하거나. 어느 쪽이 편한지는 문제마다 다르다. 폐쇄성(합집합·연결·* 연산에 대한 닫힘)은 문법 쪽이 다루기 쉽고, 인식 알고리즘과 파싱은 기계 쪽이 다루기 쉽다.

한 줄 메모. 결정적 푸시다운 오토마타(DPDA)는 모든 비결정성을 버린 변종으로, 인식하는 언어 부류는 CFL의 진부분집합이다. 예컨대 회문 언어 { wwR }는 CFL이지만 어떤 DPDA로도 받아들일 수 없다 — 가운데가 어디인지 미리 알 길이 없기 때문이다.

다음 강의에서는 CFL의 한계를 가르는 도구, 즉 문맥 자유 언어 펌핑 보조정리를 들고 와서 "이 언어는 CFL이 아니다"를 증명하는 법을 배운다. 그리고 마침내 스택 한 개의 천장을 뚫고, 무한 테이프라는 새 풍경 — 튜링 기계 — 으로 발을 들인다.