강의 2

비결정성, 폐쇄성, 정규표현식 → 유한 오토마타

갈래길에서 동시에 모든 길을 가는 기계, 그리고 그것이 결국 결정적 기계와 같다는 놀라움.

1. 비결정성이라는 사고 실험

지난 강의의 DFA는 모범생이었다. 매 단계 정확히 한 곳으로만 움직였고, 같은 입력에 대해 같은 답을 내놓았다. 이번에는 그 모범생 옆에 약간 수상한 선배 한 명을 앉혀 보자. 같은 입력 글자를 보고도 여러 상태로 동시에 갈라질 수 있는 기계, 심지어 입력을 한 글자도 읽지 않고도 상태를 바꿀 수 있는 기계. 이 선배가 바로 비결정적 유한 오토마타(NFA, Nondeterministic Finite Automaton)이다.

비결정성을 사람의 비유로 풀자면 이렇다. DFA는 길이 갈라질 때마다 한쪽을 “골라야” 한다. NFA는 그런 선택을 거부한다. 모든 갈래길에서 분신술을 써서 모든 갈래로 동시에 들어간다. 어느 한 분신이라도 끝까지 살아남아 받아들임 상태에 도달하면, 전체 NFA는 그 입력을 받아들였다고 선언한다. 한 분신이 막다른 골목에 부딪혀 사라지더라도, 다른 분신이 골인하면 그만이다.

한 줄 메모. 비결정성을 “미래를 미리 보는 마법사”로 묘사하기도 한다. 마법사는 정답으로 가는 분신만 살려 두는 듯이 보이지만, 사실은 모든 분신을 동시에 굴리고 그중 하나라도 성공하면 만세를 부른다. 결과만 보면 마법처럼 보이지만, 메커니즘은 평행 탐색일 뿐이다.

2. NFA의 형식 정의

형식적으로 비결정성을 어떻게 표현할까. 두 가지 변화가 필요하다. 첫째, 한 상태와 한 글자에서 갈 수 있는 다음 상태가 여러 개일 수 있어야 한다. 둘째, 글자를 읽지 않고도(즉 ε으로) 이동할 수 있어야 한다.

정의. Σε = Σ ∪ {ε}이라 하자. NFA는 5-튜플 N = ⟨Q, Σ, δ, q0, F⟩이며, 단 전이 함수가 δ: Q × Σε → P(Q)이다. 여기서 P(Q)는 Q의 멱집합이다.

입력 w ∈ Σ*가 주어졌을 때, w를 어떤 식으로 ε들을 사이사이 끼워 w = y1y2⋯ym (yi ∈ Σε)로 쪼갤 수 있고, 상태열 r0, r1, ⋯, rm가 r0 = q0, ri ∈ δ(ri−1, yi), rm ∈ F를 만족하면 N은 w를 받아들인다고 한다.

전이 함수의 공역이 Q가 아니라 P(Q)인 점이 핵심이다. δ(q, a) = ∅이라는 것은 “이 상태에서 a를 보면 갈 곳이 없다”라는 뜻이고, 이 분신은 거기서 사라진다. 반대로 δ(q, a) = {p1, p2, p3}이면 분신 셋이 동시에 태어난다.

예제. Σ = {0, 1}에서 “끝에서 세 번째 글자가 1인” 언어를 인식하는 NFA를 생각해 보자. DFA로 짜려면 “마지막 세 글자가 무엇이었는지” 모두 기억해야 하므로 8개에 가까운 상태가 필요하다. 그러나 NFA는 다음과 같이 단 4개의 상태로 끝낸다. 
        0,1
       ┌──┐
       ▼  │
   ──▶ q0 ──1──▶ q1 ──0,1──▶ q2 ──0,1──▶ q3((accept))
q0에서 자기 자신으로 가는 0,1 루프는 “아직 결정적 시점이 오지 않았다”라고 늑장을 부리는 분신이다. 어느 순간 1을 읽고 q1으로 갈라져 나가는 분신이 정답 분신이 된다. 정답 분신이 끝까지 살아남으려면, 우리가 갈라져 나간 그 1이 끝에서 세 번째 글자여야 한다. NFA는 “언제 갈라져야 정답인가”를 미리 알고 있는 양 행동하지만, 실제로는 모든 가능한 갈림길을 평행하게 시도하고 있을 뿐이다.

3. 부분집합 구성: NFA를 DFA로 흉내 내기

비결정성이 진짜로 새로운 능력을 추가했는가. 답은 “아니다”이다. 매 시점에 NFA의 상태가 “여러 분신의 집합”이라는 점에 착안하면, 그 집합 자체를 새로운 단일 상태로 보면 된다. 즉 NFA의 상태 집합 Q에 대해 그 멱집합 P(Q)를 새로운 DFA의 상태 집합으로 삼는다. 이를 부분집합 구성(subset construction)이라 부른다.

정리. 모든 NFA N = ⟨Q, Σ, δ, q0, F⟩에 대해 L(M) = L(N)인 DFA M이 존재한다.
증명 스케치. 임의 R ⊆ Q에 대해 ε-폐포 E(R)을 “R에서 ε-전이만으로 도달 가능한 상태들의 집합”으로 정의한다. M = ⟨Q', Σ, δ', q0', F'⟩를 다음과 같이 잡는다.
  • Q' = P(Q)
  • q0' = E({q0})
  • δ'(R, a) = E( ⋃q ∈ R δ(q, a) )
  • F' = {R ∈ Q' : R ∩ F ≠ ∅}
입력 w를 읽는 동안 M의 상태는 정확히 “지금 이 시점에 NFA의 어느 상태 분신들이 살아 있는가”의 집합과 일치한다. 받아들임 상태의 정의도 그에 맞춰 “살아 있는 분신 중 하나라도 받아들임이면 받아들이라”로 옮겨 둔 것뿐이다. 귀납으로 동치성을 어렵지 않게 확인할 수 있다. ∎

구성 자체는 깔끔하지만 대가가 있다. NFA의 상태가 n개라면 DFA의 상태는 최대 2n개까지 부풀 수 있다. 이를 상태 폭발(state explosion)이라 한다. 실제로 위 “끝에서 세 번째가 1” 예제에서, 부분집합 구성을 끝까지 적용하면 도달 가능한 부분집합만 따져도 23 = 8 정도의 상태가 등장한다. NFA는 진정 새로운 능력을 가진 것이 아니라, 같은 능력을 더 압축된 형태로 표현하는 표기법인 셈이다.

따름정리. 어떤 언어 L이 어떤 NFA에 의해 인식되는 것과, L이 정규 언어인 것은 동치다. 즉 NFA와 DFA는 인식 능력에서 정확히 같다.

4. 정규 언어의 폐쇄성

같은 클래스를 두 가지 방식으로 표현할 수 있다는 사실은 단순한 미학적 결과를 넘어선다. 어떤 연산에 대해 클래스가 닫혀 있는지 보일 때, 어느 모델이든 편리한 쪽을 골라 쓸 수 있게 되기 때문이다.

정리. 정규 언어의 클래스는 다음 연산에 대해 닫혀 있다: 합집합, 교집합, 여집합, 연결, 클레이니 스타, 역(reversal).
증명 스케치.
  • 합집합: NFA를 사용한다. L1, L2를 인식하는 NFA N1, N2에 새 시작 상태 s를 두고 ε-전이로 두 NFA의 시작 상태에 동시에 분기시킨다. 분신 둘 중 하나만 받아들이면 충분하다.
  • 연결: 같은 N1, N2에 대해 N1의 모든 받아들임 상태에서 N2의 시작 상태로 ε-전이를 추가하고, N2의 받아들임만을 받아들임으로 둔다. “먼저 L1을 끝낸 뒤 L2를 시작” 시나리오를 그대로 그림으로 옮긴 것이다.
  • 스타: N1에 새 시작 상태 s′을 두고 받아들임으로 지정해 ε(빈 문자열)을 인정한다. s′에서 N1의 시작 상태로 ε-전이를 두고, N1의 모든 받아들임 상태에서 다시 N1의 시작으로 ε-전이를 보낸다. 한 바퀴를 돌 때마다 새로운 한 조각이 이어진다.
  • 여집합: DFA를 사용한다. 받아들임 집합 F를 Q ∖ F로 뒤집으면 끝난다. 이 단순함은 “모든 입력에 대해 정확히 한 경로가 존재하는” 결정성 덕분이다. 같은 트릭을 NFA에 그대로 적용하면 망한다.
  • 교집합: 곱 구성(product construction). DFA M1, M2에 대해 상태를 (q1, q2) ∈ Q1 × Q2로 두고 두 기계를 병렬로 굴린다. 두 기계가 모두 받아들이는 쌍이 받아들임 상태다. 또는 드모르간으로 합집합과 여집합으로부터 끌어낼 수도 있다.
  • 역: NFA에서 모든 화살의 방향을 뒤집고, 받아들임과 시작의 역할을 바꾼다. 다중 받아들임을 처리하기 위해 새 시작 상태와 ε-전이가 필요할 수 있다.
각 경우 모두 새로 만든 기계가 원하는 언어를 정확히 인식함을 귀납으로 확인하면 된다. ∎
한 줄 메모. 합집합·연결·스타에는 NFA가, 여집합·교집합에는 DFA가 편하다. 같은 클래스를 둘로 표현해 두는 가치가 여기서 빛난다. 모델은 상황에 맞게 갈아 끼우면 된다.

5. 정규 표현식 → NFA: 톰슨 구성

정규 표현식과 유한 오토마타가 같은 클래스를 표현한다는 큰 정리의 한쪽 방향을 처리하자. 즉 임의의 정규 표현식 R로부터 L(N) = L(R)인 NFA N을 만들 수 있음을 보인다. 정규 표현식의 정의가 귀납적이므로 구성도 귀납적이다. 이 방법을 톰슨 구성(Thompson’s construction)이라 한다.

정리. 모든 정규 표현식 R에 대해 L(N) = L(R)인 NFA N이 존재한다. 따라서 정규 표현식이 표현하는 모든 언어는 정규 언어다.
증명 스케치. R의 구조에 대한 귀납.

기저. R = ∅이면 받아들임 상태가 없는 두 상태 NFA. R = ε이면 시작 상태가 곧 받아들임 상태이며 모든 a ∈ Σ에 대한 전이가 비어 있다. R = a (a ∈ Σ)이면 시작에서 a 화살로 받아들임으로 가는 두 상태 NFA.

귀납. R1, R2에 대해 NFA N1, N2를 이미 가졌다고 하자.

  • R1 ∪ R2: 새 시작 상태에서 N1, N2의 시작 상태로 각각 ε-전이를 두 갈래 보낸다. 두 NFA의 받아들임을 그대로 받아들임으로 유지한다.
  • R1R2: N1의 받아들임을 받아들임에서 풀고, 거기서 N2의 시작으로 ε-전이를 보낸다. N2의 받아들임만 새로운 받아들임이 된다.
  • R1*: 새 시작 상태 s′을 두고 동시에 받아들임으로 지정하여 ε(0회 반복)을 처리한다. s′에서 N1의 시작으로 ε-전이를 보내고, N1의 모든 받아들임에서 다시 N1의 시작으로 ε-전이를 두어 “여러 번” 반복할 수 있게 한다.
각 단계마다 ε-전이로 두 부분 NFA를 끼워 맞추는 모양새가 마치 작은 부품을 클레이니로 조립하는 모양이다. 부품이 망가지지 않도록 “시작 상태로 들어오는 화살 없음, 받아들임 상태에서 나가는 화살 없음”이라는 불변량을 유지하는 것이 깔끔한 구성의 비결이다. ∎
예제. R = (ab)*는 다음 부품 조립으로 얻어진다. 먼저 a, b 각각의 두 상태 NFA를 만들고, 연결로 ab의 NFA를 만든다. 거기에 스타 구성을 한 번 적용해 (ab)*의 NFA를 얻는다. ε-전이가 다소 무성하게 자라지만, 부분집합 구성을 굳이 거치지 않더라도 NFA 그대로 시뮬레이션할 수 있으니 실용상 문제없다.

6. 다음 강의 예고

이 시점에서 우리는 정규 언어를 향한 두 갈래 등산로—DFA/NFA와 정규 표현식—를 한쪽 방향(정규 표현식 → NFA)으로 연결했다. 다음 강의에서는 반대 방향(DFA → 정규 표현식)을 매듭짓고, 더 무거운 질문 하나를 들고 온다. 정규 언어가 아닌 언어가 존재하는가, 있다면 어떻게 증명하는가. 그 답은 비둘기집 원리가 살짝 변장한 모습으로 등장하는 펌핑 보조정리에서 나온다. 그 다음에는 한 단계 더 큰 사다리에 발을 올려, 균형 괄호처럼 정규 언어가 도저히 잡지 못하는 언어들을 잡아내는 문맥 자유 문법(CFG)으로 이행할 것이다.