강의 7

오토마타와 문법의 결정 문제

"이 기계가 이 문자열을 받아들이나요?" — 답할 수 있는 질문들의 카탈로그.

1. 결정 문제라는 장르

결정 문제(decision problem)란 예/아니오로 답이 떨어지는 질문이다. 우리는 이 질문들을 언어로 인코딩한다. 예컨대 "DFA B가 문자열 w를 수락하는가?"는 다음 언어의 멤버십 문제와 같다.

ADFA = { ⟨B, w⟩ : B는 DFA이고 B가 w를 수락한다 }

여기서 ⟨B, w⟩는 DFA B의 형식적 표현과 입력 w를 한 문자열로 인코딩한 것이다. 어떤 인코딩 규약이든 — 예컨대 상태와 전이 함수를 ASCII 표로 적고 # 같은 구분자로 잇든 — 합리적이기만 하면 결정 가능 여부는 바뀌지 않는다(처치-튜링 명제의 일상적 활용 사례다).

이번 강의의 모든 정리는 같은 골격을 따른다: "어떤 TM이 입력을 받아 알고리즘적 절차를 수행하고 항상 멈추며, 답이 예일 때 정확히 수락한다." 이러한 TM이 존재함을 보이면 해당 언어는 결정 가능(decidable)이다.

2. ADFA: 시뮬레이션 한 번이면 끝

정리 7.1. ADFA는 결정 가능하다.
증명. 다음 TM MA·DFA를 정의한다.

입력 ⟨B, w⟩에 대해:
  1. 인코딩이 잘 형성되었는지 검사한다. 아니라면 거부한다.
  2. B의 시작 상태 q0를 현재 상태로 둔다.
  3. w의 각 글자 wi에 대해 차례로 현재 상태를 δ(q, wi)로 갱신한다.
  4. 입력을 다 읽은 뒤 현재 상태가 수락 상태이면 수락, 아니면 거부.
DFA는 입력 한 글자당 한 단계만 진행하므로 n = |w|에 대해 O(n)단계 이하로 항상 멈춘다. 따라서 MA·DFA는 결정자(decider)다. ∎

이 증명은 거의 무의미해 보일 정도로 평이하다. 그러나 메시지는 분명하다: 유한한 자원만으로 정의되는 모델을 흉내 내는 일은 항상 결정 가능하다. 이 패턴이 이번 강의 절반의 동력이 된다.

3. EDFA: 그래프 탐색의 변장

EDFA = { ⟨B⟩ : B는 DFA이고 L(B) = ∅ }

DFA가 어떤 문자열도 수락하지 않는다는 것은, 시작 상태에서 어떤 수락 상태에도 도달할 수 없다는 것과 동치이다. 그리고 도달 가능성은 그래프에서 너비 우선 탐색(BFS)이면 된다.

정리 7.2. EDFA는 결정 가능하다.
증명.

입력 ⟨B⟩에 대해:
  1. B의 상태 집합 가운데 시작 상태 q0만 표시(mark)한다.
  2. 표시된 어떤 상태로부터 한 전이로 도달하는 상태가 있으면, 그 상태도 표시한다. 더 이상 새로 표시할 상태가 없을 때까지 반복한다.
  3. 표시된 상태 중에 수락 상태가 하나라도 있으면 거부, 없으면 수락.
상태 수가 유한하므로 단계 2의 반복은 유한 번 만에 끝난다. 표시된 집합은 정확히 시작 상태에서 도달 가능한 상태들이고, 그 안에 수락 상태가 없을 때 정확히 L(B) = ∅이다. ∎
한 줄 메모. 마지막 줄에 "수락"과 "거부"가 뒤집힌 것에 주목하자. EDFA는 "L이 비어 있다"가 예인 언어이므로, 수락 상태에 도달할 수 있으면 비어 있지 않으므로 거부해야 한다.

4. EQDFA: 대칭차의 마법

EQDFA = { ⟨A, B⟩ : A, B는 DFA이고 L(A) = L(B) }

두 언어가 같음을 직접 비교하는 것은 어렵다 — 무한히 많은 문자열에 대해 일치를 확인해야 할 것 같다. 하지만 집합론적 정체성 하나로 문제가 단번에 풀린다.

L(A) = L(B) ⟺ (L(A) ∖ L(B)) ∪ (L(B) ∖ L(A)) = ∅

이 우변에 등장하는 집합을 두 언어의 대칭차(symmetric difference)라 부르고 L(A) △ L(B)로 적는다. 두 언어가 다르면, 한 쪽에는 있고 다른 쪽에는 없는 어떤 문자열이 반드시 존재한다 — 그 문자열이 대칭차에 들어 있다.

정리 7.3. EQDFA는 결정 가능하다.
증명.

입력 ⟨A, B⟩에 대해:
  1. 정규 언어가 합집합·교집합·여집합 연산에 대해 닫혀 있으므로(강의 1·2의 결과), L(A) △ L(B)를 인식하는 DFA C를 곱 구성(product construction)으로 만든다.
  2. 정리 7.2의 알고리즘을 ⟨C⟩에 적용해 L(C) = ∅인지 판정한다.
  3. ⟨C⟩가 EDFA에 속하면 수락, 아니면 거부.
모든 단계가 결정 가능한 절차이므로 전체도 결정 가능하다. ∎
한 줄 메모. 두 결정 가능 언어를 도구로 또 다른 결정 가능 언어를 푼다. 결정 가능성은 모듈식으로 조립된다.

5. NFA와 정규 표현식: 변환 한 단계 추가

ANFA = { ⟨N, w⟩ : N이 w를 수락 },    ENFA = { ⟨N⟩ : L(N) = ∅ }

정리 7.4. ANFA, ENFA, EQNFA는 모두 결정 가능하다. 또한 정규 표현식 R에 대한 AREX = { ⟨R, w⟩ : R이 w를 생성 }도 결정 가능하다.
증명 스케치. 각 입력을 받아 부분 알고리즘으로 DFA로 변환한 뒤 정리 7.1–7.3을 호출한다. NFA → DFA 변환은 부분집합 구성(subset construction)으로, 정규 표현식 → NFA 변환은 톰슨 구성(Thompson's construction)으로 수행한다. 두 변환 모두 알고리즘적이고 항상 멈춘다. ∎

변환의 비용(상태 수가 지수적으로 폭발할 수 있음)은 결정 가능성에는 영향을 주지 않는다. 결정 가능성은 "유한 시간 안에 답이 나오느냐"의 문제이지 "얼마나 빠르냐"의 문제가 아니다. 후자는 복잡도 이론의 영역이다.

6. 문맥 자유 문법으로

ACFG = { ⟨G, w⟩ : CFG G가 w를 생성 }

여기서 첫 번째 함정이 등장한다. 순진하게 "G가 가능한 모든 유도(derivation)를 시도해보자"고 하면 끝없이 늘어나는 유도가 무한히 많을 수 있어 절차가 멈추지 않는다. 그러나 한 가지 관찰로 문제가 풀린다.

정의 7.5 (촘스키 정규형, CNF). CFG G가 촘스키 정규형(Chomsky normal form)이라 함은 모든 규칙이 다음 형태 중 하나일 때이다.
  • A → BC    (단, B, C는 시작 변수가 아닌 변수)
  • A → a    (단, a는 단말 기호)
  • S → ε    (필요 시 시작 변수에 한해)

모든 CFG는 같은 언어(필요시 ε 처리만 분리)를 생성하는 어떤 CNF로 알고리즘적으로 변환할 수 있다(보조 변수 도입, 단위 규칙 제거, ε 규칙 제거 단계의 조합). 이제 결정적 사실 하나가 마법을 부린다.

보조정리 7.6. CNF인 CFG G가 길이 n ≥ 1인 문자열 w를 생성한다면, 어떤 유도든 정확히 2n − 1 단계로 이루어져 있다.

이유는 직관적이다. CNF에서 단말은 "A → a" 규칙으로만 나타나므로 길이 n인 문자열에는 단말 규칙이 정확히 n번 적용된다. 비단말 규칙 "A → BC"는 변수 한 개를 두 개로 늘리므로 변수 수를 1 증가시킨다. 시작 변수 1개에서 출발해 변수 n개까지 늘리려면 정확히 n − 1번 적용되어야 한다. 합치면 (n − 1) + n = 2n − 1.

정리 7.7. ACFG는 결정 가능하다.
증명.

입력 ⟨G, w⟩에 대해:
  1. G를 동치인 CNF G′로 변환한다.
  2. w = ε이면 G′에 S → ε이 있는지 보고 그에 따라 수락/거부한다.
  3. 그 외에는 G′의 규칙을 사용해 길이 2|w| − 1 이하의 모든 유도를 나열하고, 그 가운데 w를 생성하는 것이 있는지 확인한다.
  4. 있으면 수락, 없으면 거부.
나열할 유도 후보의 수는 유한하므로 절차는 항상 멈춘다. ∎

실용적인 사람들은 단계 3을 그렇게 야만적으로 짜지 않는다. 동적 계획법으로 만든 CYK(Cocke-Younger-Kasami) 알고리즘은 O(n3)시간에 같은 문제를 푼다 — 길이 k의 모든 부분 문자열이 어떤 변수에서 유도되는지를 작은 k부터 채워 올라간다. 결정 가능성을 보이는 데에는 야만적인 나열로 충분하지만, 컴파일러를 짤 때는 CYK 또는 LR(1) 같은 더 빠른 파싱이 등장한다.

7. ECFG: 단말 도달 가능성

ECFG = { ⟨G⟩ : CFG G이고 L(G) = ∅ }

이 문제도 도달 가능성의 변장이다. 다만 이번 그래프는 변수와 규칙의 그래프다.

정리 7.8. ECFG는 결정 가능하다.
증명.

입력 ⟨G⟩에 대해:
  1. 처음에는 어떤 변수도 표시되지 않은 상태로 시작한다.
  2. "규칙 A → X1X2…Xk의 모든 Xi가 (단말이거나) 이미 표시된 변수일 때, A를 표시한다." 새로 표시할 변수가 없을 때까지 반복한다.
  3. 시작 변수 S가 표시되었으면 거부, 아니면 수락.
"표시된 변수" = "어떤 단말 문자열을 적어도 하나 생성할 수 있는 변수". 따라서 S가 표시되지 않는 것이 정확히 L(G) = ∅과 동치이다. 변수 수가 유한하므로 단계 2는 유한 번 만에 종료된다. ∎

8. 풀 수 없는 한 가지: EQCFG

여기까지 보면 도구를 충분히 갖춘 듯 느껴진다. 그러면 EQCFG = { ⟨G1, G2⟩ : L(G1) = L(G2) }도 같은 트릭으로 풀릴까? 두 문맥 자유 언어의 대칭차도 결정 가능한 비어 있음 검사로 환원할 수 있을까?

아쉽게도 안 된다. 문맥 자유 언어는 합집합과 연쇄에는 닫혀 있지만 교집합과 여집합에는 닫혀 있지 않다. 따라서 대칭차 트릭이 무너진다. 이것은 단순히 우리의 구성이 통하지 않는다는 뜻이지만, 더 깊은 진실은 다음과 같다.

정리 7.9 (예고). EQCFG는 결정 불가능(undecidable)하다.

이 정리의 증명은 환원(reduction) 기법을 본격적으로 다룬 뒤에야 가능하다. 한편 모든 문맥 자유 언어가 (CYK가 보여주듯) 결정 가능한 멤버십을 가지므로 EQCFG는 결정 가능 언어 사이의 동치 문제다. 결정 가능 언어 두 개의 동치성마저 일반적으로는 결정 불가능할 수 있다는 사실을 살짝 미리 들고 가자.

한 줄 메모. 또 하나, ACFG·ECFG가 결정 가능하다는 사실의 따름정리 — 모든 문맥 자유 언어는 결정 가능하다. CFG가 주어지면 멤버십을 항상 알고리즘적으로 판단할 수 있다.

9. 다음 강의로

지금까지 우리는 결정 가능의 풍요로운 정원을 거닐었다. 거기에는 시뮬레이션, 그래프 탐색, 곱 구성, 정규형 변환 같은 점잖은 도구들이 있었다. 다음 강의 8에서는 정원의 담장을 처음으로 넘는다 — 결정 불가능한 언어가 존재함을, 심지어 우리에게 가장 친숙한 질문 "M이 w를 수락하는가?"가 일반적으로는 알고리즘으로 풀리지 않음을 보일 것이다. 도구는 단 하나, 칸토어의 대각선 논법이다.