강의 3

정규 펌핑 보조정리, 유한 오토마타 → 정규표현식, 문맥 자유 문법

유한한 메모리의 한계를 폭로하고, 그 너머의 풍경으로 한 발 내딛는다.

1. 펌핑 보조정리: 한계의 증명서

지금까지의 강의는 “할 수 있는 것”을 늘어놓는 자리였다. 이번 절은 자세를 바꾼다. 정규 언어가 할 수 없는 일을 명시적으로 증명하기 위한 도구를 만든다. 이름은 거창하지만 그 본질은 한 줄로 요약된다. 유한한 메모리는 결국 같은 상태를 반복하게 되어 있다.

정리(정규 언어의 펌핑 보조정리). L이 정규 언어이면 어떤 정수 p ≥ 1(펌핑 길이, pumping length)이 존재하여, |s| ≥ p인 모든 s ∈ L은 다음을 만족하도록 s = xyz로 쪼갤 수 있다.
  1. 모든 i ≥ 0에 대해 xyiz ∈ L
  2. |y| > 0
  3. |xy| ≤ p
증명 스케치. L을 인식하는 DFA M이 있다고 하자. M의 상태 수를 p로 둔다. |s| ≥ p인 임의 s ∈ L에 대해 M이 s를 처리하며 거치는 상태열을 r0, r1, ⋯, r|s|라 하면, 처음 p+1개의 상태 r0, ⋯, rp 중 어딘가는 같은 상태가 두 번 나타난다(비둘기집 원리). 즉 j < k ≤ p인 j, k에 대해 rj = rk.

이제 s = xyz를 x = s1⋯sj, y = sj+1⋯sk, z = sk+1⋯s|s|로 잡자. y는 rj에서 rk로 가는 사이클을 그리고, rj = rk이므로 이 사이클은 0번 돌든 100번 돌든 무관하게 같은 출발/도착 상태를 유지한다. 따라서 임의 i ≥ 0에 대해 xyiz를 읽었을 때 결국 r|s| ∈ F에 도달한다. |y| > 0(j < k), |xy| = k ≤ p가 모두 성립한다. ∎

한 줄로 다시 적어 두자. 유한 상태 기계가 충분히 긴 입력을 처리하면 같은 상태를 두 번 거치게 되며, 그 사이의 부분 문자열은 마음대로 펌프질해도(반복하거나 통째로 지워도) 받아들임 여부가 변하지 않는다. 비둘기집 원리가 자동기계의 옷을 갈아입은 모습이다.

한 줄 메모. 펌핑 보조정리는 “정규성이면 펌핑 가능”의 한 방향만 말한다. 그 역은 거짓이다. 펌핑이 가능하다고 정규인 것은 아니다. 따라서 이 보조정리는 “비정규성을 증명하는” 무기로만 쓰는 것이 안전하다.

2. 비정규성의 살벌한 시범: { anbn : n ≥ 0 }

도구를 손에 쥐었으니 시연을 한 번 해 보자. Σ = {a, b}에서 L = {anbn : n ≥ 0}이 정규가 아님을 증명한다. 직관적으로 이 언어를 인식하려면 a를 몇 개 봤는지 정확히 세어 두어야 하는데, 유한 메모리로는 임의로 큰 카운터를 흉내낼 수 없다는 것이 핵심이다. 이를 펌핑 보조정리로 정밀하게 표현한다.

주장. L = { anbn : n ≥ 0 }은 정규 언어가 아니다.
증명. 모순을 위해 L이 정규라 가정하자. 펌핑 보조정리로 어떤 펌핑 길이 p가 존재한다. 문자열 s = apbp를 고른다. |s| = 2p ≥ p, s ∈ L이므로 보조정리의 가설을 만족한다.

보조정리에 따라 s = xyz, |xy| ≤ p, |y| > 0, ∀i xyiz ∈ L이 되도록 쪼갤 수 있다. 그런데 |xy| ≤ p이므로 xy는 모두 a들로만 이루어져 있다. 즉 y = ak(어떤 k ≥ 1)이다.

이제 i = 2를 적용해 보자. xy2z = ap+kbp는 a의 개수와 b의 개수가 더 이상 같지 않다(p+k ≠ p, k ≥ 1). 따라서 xy2z ∉ L. 그러나 보조정리는 xy2z ∈ L이어야 한다고 단언했으므로 모순. 가정이 틀렸다. ∎

증명 한 토막에서 가져갈 교훈. 펌핑 보조정리는 “적이 길이 p를 골라 주면 우리가 도전 문자열 s를 골라야 한다”는 일종의 이인 게임이다. s를 영리하게 고르면(가능한 한 “나누기 어려운” 문자열로) 적이 어떻게 쪼개든 i를 적당히 골라 모순을 만들 수 있다. 이 책에서는 자주 등장하는 패턴이니 손에 익혀 두는 편이 좋다.

한 줄 메모. 비슷한 방법으로 { ww : w ∈ {0,1}* }, { 0n1n2n }, 그리고 “회문(palindrome) 전체” 같은 언어들이 비정규임을 보일 수 있다. 공통 주제는 “두 곳 사이의 동일성을 임의로 큰 범위에서 강제”하는 구조라는 점이다. 유한 상태로는 결코 잡히지 않는 종류의 제약이다.

3. DFA → 정규 표현식: GNFA 상태 제거법

지난 강의에서 정규 표현식을 NFA로 옮기는 톰슨 구성을 보았다. 이번엔 반대 방향이다. 일반화 NFA(GNFA, Generalized NFA)를 거쳐 DFA에서 정규 표현식을 뽑아낸다.

GNFA란 화살의 라벨이 단일 글자가 아니라 임의의 정규 표현식인 NFA다. 추가로 다음 정형(normal form)을 가정해 두면 작업이 깔끔해진다.

주어진 DFA M으로부터 시작 상태 s′와 받아들임 상태 a′를 새로 추가하고 ε-전이로 연결하면, 어렵지 않게 위 정형의 GNFA를 얻을 수 있다. 이제 핵심 보조 명제는 다음이다.

보조정리(상태 제거). GNFA G가 위 정형을 만족하고 상태 수가 ≥ 3이면, G에서 어떤 한 상태 qrip(s′, a′이 아닌)을 “지워 버리는” 새로운 GNFA G′을 만들 수 있다. G′의 상태 수는 G보다 하나 적으며 L(G′) = L(G)다.
증명 스케치(한 단계 워크스루). 지울 상태를 qrip라 하자. qrip를 거치는 모든 경로는 “어떤 다른 상태 qi에서 qrip로 들어와, qrip에서 자기 자신으로 임의 횟수 머문 뒤, 어떤 qj로 빠져나가는” 형태다. 라벨 정규 표현식을 각각 R1 = (qi → qrip), R2 = (qrip → qrip), R3 = (qrip → qj), R4 = (qi → qj의 기존 라벨)이라 하자.

G′에서 (qi → qj)의 새 라벨을

R4 ∪ R1 R2* R3

로 둔다. 이 표현식은 “qrip를 거치지 않고 가는 길(R4) 또는 qrip를 통과해 가는 길(R1 다음 R2를 임의 회 반복한 뒤 R3)” 양쪽을 정확히 모두 포착한다. 모든 i, j 쌍에 대해 동시에 이 갱신을 한 다음 qrip와 그에 인접한 모든 화살을 통째로 지워 버리면 된다. 동치성은 임의 입력 w가 G에서 받아들여지는 길과 G′에서 받아들여지는 길이 일대일 대응됨을 길의 모양에 따라 case 분석하면 확인된다. ∎

이 절차를 qrip를 하나씩 골라가며 상태가 둘(시작 s′와 받아들임 a′)만 남을 때까지 반복한다. 마지막에 남은 (s′ → a′) 화살의 라벨이 곧 L(M)을 표현하는 정규 표현식이다.

예제(미니 워크스루). 상태 q0(시작/받아들임), q1로 이루어진 두 상태 DFA가 다음 전이를 가진다고 하자. δ(q0, a) = q1, δ(q1, a) = q0, δ(q0, b) = q0, δ(q1, b) = q1. 이 DFA는 “a가 짝수 개 있는 {a,b}* 위 문자열”을 인식한다. 새 시작 s′와 받아들임 a′을 ε으로 연결한 GNFA를 만들고 q1을 제거하면, q0 → q0의 자기 루프 라벨이

b ∪ a b* a

가 된다. 이어서 q0도 제거하면 s′ → a′의 라벨이

(b ∪ a b* a)*

로 나온다. 곱씹어 보면 “b를 마음대로 끼워 넣되, a들은 짝을 이뤄 b로 패딩된 채 나타난다”라는 직관과 정확히 들어맞는다.
정리. 어떤 언어 L에 대해 다음 셋은 동치다.
  1. L은 정규 언어다(어떤 DFA가 인식한다).
  2. L은 어떤 NFA가 인식한다.
  3. L은 어떤 정규 표현식이 표현한다.

이로써 우리는 정규 언어라는 봉우리에 오르는 세 등산로—DFA, NFA, 정규 표현식—가 모두 같은 정상에 닿는다는 그림을 완성했다. 펌핑 보조정리는 그 정상의 고도가 어디까지인지(즉 무엇을 못 하는지) 알려준다.

4. 더 큰 사다리: 문맥 자유 문법

{ anbn }이 정규가 아니라는 사실은 두 가지 반응을 부른다. 한쪽은 “그러면 됐다, 우리는 정규 언어만으로 충분하다”라고 손을 털 것이고, 다른 한쪽은 “그렇다면 그 너머를 잡아내는 더 강한 모델이 필요하다”라고 팔을 걷어붙일 것이다. 후자의 길로 들어선 첫 정류장이 문맥 자유 문법(CFG, Context-Free Grammar)이다. 균형 괄호, 산술식의 결합 구조, 프로그래밍 언어의 구문—이 모든 것이 CFG의 영역이다.

정의. CFG는 4-튜플 G = ⟨V, Σ, R, S⟩이다.
  • V: 변수(variable, 비단말 nonterminal)들의 유한 집합
  • Σ: 단말(terminal) 기호들의 유한 집합. V ∩ Σ = ∅
  • R: 규칙(rule)들의 유한 집합. 각 규칙은 A → α 형태이며 A ∈ V, α ∈ (V ∪ Σ)*
  • S ∈ V: 시작 변수(start variable)
문자열 u, v, w ∈ (V ∪ Σ)*에 대해 u가 v를 규칙 한 번에 의해 치환해 얻어졌다면 u ⇒ v라 쓴다. 0번 이상의 단계로 얻어졌다면 u ⇒* v라 쓴다. G가 생성하는 언어는 L(G) = {w ∈ Σ* : S ⇒* w}.

유도(derivation)란 시작 변수 S에서 규칙을 차례로 적용해 단말 문자열에 도달하는 한 편의 이야기다. 같은 단말 문자열 w를 만들어 내는 유도가 여러 가지일 수 있는데, 그중 “서로 다른 트리 모양에 해당하는” 본질적으로 다른 유도가 둘 이상 존재할 때 그 문자열은 G에서 모호(ambiguous)하다고 한다. 그리고 유도의 트리 모양 자체를 파스 트리(parse tree)라 부른다. 트리의 뿌리는 S, 내부 노드는 변수, 잎은 단말이며, 각 내부 노드의 자식들은 그 노드에서 적용된 규칙의 우변과 일치한다.

예제 1(균형 괄호). Σ = { (, ) }, V = {S}, 시작 S, 규칙

S → (S) | SS | ε

이 G는 모든 균형 잡힌 괄호 문자열들의 언어를 생성한다. 예를 들어 “(())()”의 유도는

S ⇒ SS ⇒ (S)S ⇒ ((S))S ⇒ (())S ⇒ (())(S) ⇒ (())().

한편 이 문법은 모호하다. 같은 “()()()” 같은 문자열에 대해 SS를 어디서 쪼개느냐에 따라 본질적으로 다른 트리가 여러 개 만들어진다. 모호성은 종종 의미 해석의 골칫거리가 되므로 실제 컴파일러용 문법에서는 모호성을 제거하도록 설계한다.
예제 2({ anbn : n ≥ 0 }). 펌핑 보조정리로 정규가 아님을 보였던 그 언어가, CFG에서는 단 두 줄로 우아하게 잡힌다.

S → aSb | ε

유도를 보면 매 단계마다 a 하나와 b 하나가 정확히 짝을 이루어 추가되므로 결과 문자열의 a 개수와 b 개수가 항상 일치한다. 정규 언어가 도저히 셀 수 없었던 그 짝 맞춤을, “문법”이라는 더 풍부한 형식이 단번에 처리해 버린다.
정의. 어떤 CFG가 생성하는 언어를 문맥 자유 언어(CFL, Context-Free Language)라 한다. 모든 정규 언어는 CFL이지만(증명: DFA를 흉내 내는 우선형 문법으로 옮기면 된다), 그 역은 거짓이다(예: { anbn }).
한 줄 메모. 모호성은 “언어의 성질”이 아니라 “문법의 성질”이다. 같은 언어를 생성하는 문법 중 모호한 것과 모호하지 않은 것이 동시에 있을 수 있다. 한편 어떠한 모호하지 않은 CFG로도 생성될 수 없는 본질적으로 모호한(inherently ambiguous) CFL도 존재한다는 사실은 별도의 정리로 다룬다.

5. 다음 강의 예고

이번 강의로 정규 언어의 영토를 사방에서 둘러보고, 그 너머에 펼쳐진 문맥 자유 언어라는 새 대륙으로 첫발을 디뎠다. 다음 강의에서는 CFG에 대응하는 자동기계인 푸시다운 오토마타(PDA)를 도입해 “스택이라는 한 줄짜리 무한 메모리”가 어떤 능력을 추가해 주는지 살핀다. 그리고 CFL에도 그들만의 펌핑 보조정리(흔히 문맥 자유 펌핑 보조정리)가 있어, 이번에는 CFL이 아닌 언어의 존재—예컨대 { anbncn }—를 증명할 무기로 사용된다는 점도 보게 될 것이다. 사다리는 아직 끝나지 않았다.