강의 1

유한 오토마타와 정규 표현식 입문

메모리가 유한한 기계가 할 수 있는 일은 어디까지인가.

1. 계산이란 무엇인가

“계산”이라는 단어는 일상에서 너무 자주 쓰여 오히려 무덤덤하게 들린다. 그러나 계산이론(theory of computation)이 던지는 질문은 결코 무덤덤하지 않다. 어떤 문제가 기계로 풀릴 수 있는가, 그리고 풀린다면 얼마만큼의 자원이 필요한가. 이 질문에 정직하게 답하려면 먼저 “기계”라는 말의 뜻부터 못박아야 한다.

철학적인 만담으로 빠지기 전에 한 가지 영리한 결정을 내려 두자. 우리는 가장 강력한 모델, 예컨대 임의 크기의 메모리를 가진 튜링 기계(Turing machine)부터 시작하지 않는다. 오히려 그 반대다. 가장 단순한 모델—메모리가 유한한 작은 기계—에서 출발한다. 단순한 세계에서 무엇이 가능하고 무엇이 불가능한지 정확히 그려낸 다음, 한 단계씩 능력을 키워 가며 그 경계가 어떻게 변하는지를 추적할 것이다. 작은 사다리부터 차례로 밟는 것이 절벽을 단번에 넘는 것보다 훨씬 멀리 데려다 준다.

그 가장 단순한 모델이 바로 유한 오토마타(finite automaton)다. 신호등의 상태 전환, 자동판매기의 잔돈 계산, 어휘 분석기의 토큰 인식—이런 것들이 본질적으로 유한 오토마타의 작동 방식이다. 너무 단순해 보일지 모르지만, 단순하다는 것은 곧 명료하게 분석할 수 있다는 뜻이기도 하다.

한 줄 메모. 단순한 모델을 먼저 정복하는 이유는 야망이 부족해서가 아니다. 그 단순한 세계에 이미 비자명한 한계가 존재하며, 그 한계를 정확히 짚어내는 것이 더 큰 모델을 이해하는 열쇠가 된다.

2. 알파벳, 문자열, 언어

기계가 다루는 입력을 형식화해 두자. 알파벳(alphabet) Σ는 유한하고 공집합이 아닌 기호들의 집합이다. 흔히 Σ = {0, 1} (이진 알파벳), Σ = {a, b}, 혹은 Σ = {a, b, ⋯, z}와 같이 쓴다. 문자열(string)은 Σ의 원소를 유한 번 이어 붙인 수열이며, 길이 0인 빈 문자열은 ε로 표기한다. 문자열 w의 길이는 |w|로 쓴다.

정의. 알파벳 Σ에 대하여 Σ* = {w : w는 Σ의 기호로 이루어진 유한 길이 문자열}로 정의한다. 즉 Σ*는 ε을 포함한 모든 유한 문자열의 집합이다. 언어(language)란 Σ*의 부분집합 L ⊆ Σ*이다.

정의가 살짝 김빠질 수 있다. “언어”라는 거창한 단어 뒤에 숨은 것이 결국 문자열들의 집합 하나라니. 그러나 이 가벼운 정의가 무거운 일을 한다. 우리가 “문제를 푼다”라고 말하는 행위가 “주어진 입력 w가 어떤 정해진 집합 L에 속하는지 결정한다”라는 행위와 일대일로 대응되기 때문이다. 소수 판별 문제도, 문법 검사도, 컴파일러의 토큰 인식도 모두 이 형태로 다듬을 수 있다. 언어를 다루는 기계를 이해하면 결국 “문제를 푸는 기계”를 이해하게 된다.

예제. Σ = {0, 1}일 때 L1 = {w ∈ Σ* : w는 짝수 개의 1을 포함}, L2 = {0n1n : n ≥ 0}는 모두 Σ*의 부분집합이다. 둘 다 형식적으로 “언어”이지만, 곧 보겠지만 이 둘은 기계의 능력 면에서 완전히 다른 무게 등급에 속한다.

3. 결정적 유한 오토마타(DFA)

유한 오토마타의 가장 절제된 형태부터 보자. 결정적 유한 오토마타(DFA, Deterministic Finite Automaton)는 입력 문자열을 왼쪽에서 오른쪽으로 한 글자씩 읽으며, 각 단계에서 “현재 상태”라는 하나의 정보만을 기억한다. 상태의 수는 유한하다. 다음 상태는 현재 상태와 읽은 글자에 의해 유일하게 결정되므로 이름에 “결정적(deterministic)”이라는 수식이 붙는다.

정의. DFA는 5-튜플 M = ⟨Q, Σ, δ, q0, F⟩이다.
  • Q: 상태들의 유한 집합
  • Σ: 입력 알파벳
  • δ: Q × Σ → Q, 전이 함수(transition function)
  • q0 ∈ Q: 시작 상태(start state)
  • F ⊆ Q: 받아들임 상태들의 집합(accept states)
입력 w = a1a2⋯an에 대해 상태 수열 r0, r1, ⋯, rn을 r0 = q0, ri = δ(ri−1, ai)로 정의하자. rn ∈ F이면 M은 w를 받아들인다(accepts)고 한다. M이 받아들이는 모든 문자열의 집합을 L(M)이라 쓰고, 이를 M이 인식하는 언어라 부른다.

전이 함수는 이름은 거창해도 결국 “상태와 글자의 쌍을 다음 상태로 보내는 표”에 불과하다. 머릿속으로 그리려면 다음과 같은 그림이 편하다. 동그라미는 상태, 화살표는 전이, 화살표 머리에 입력 글자를 적는다. 시작 상태에는 어디서 들어오는 화살이 하나 있고, 받아들임 상태에는 이중 동그라미를 두른다.

예제 1. Σ = {a, b}에서 “문자열이 정확히 ab로 끝나는” 언어 L = {w ∈ {a,b}* : w = xab, x ∈ {a,b}*}를 인식하는 DFA를 구성한다. 핵심 통찰은 “직전에 본 글자가 무엇인가”만 기억하면 충분하다는 점이다.
  • q0: 아직 의미 있는 접미사 없음(또는 직전 글자가 a, b가 아님)
  • q1: 직전 글자가 a
  • q2: 직전 두 글자가 ab (받아들임 상태)
전이는 다음과 같이 둔다. 
       a            b
q0 ─────▶ q1   q0 ─────▶ q0
q1 ─────▶ q1   q1 ─────▶ q2
q2 ─────▶ q1   q2 ─────▶ q0
F = {q2}, q0이 시작 상태다. 잠시 손으로 “aab”, “abb”, “bab”을 추적해 보면 정확히 ab로 끝나는 입력만 q2에서 멈춘다는 사실이 확인된다.
예제 2. Σ = {0, 1}에서 “1의 개수가 3의 배수인” 언어를 인식하는 DFA. 상태 rk(k ∈ {0,1,2})를 “지금까지 읽은 1의 개수 mod 3 = k”로 둔다.
  • δ(rk, 0) = rk (0은 카운터를 건드리지 않음)
  • δ(rk, 1) = r(k+1) mod 3
시작 상태는 r0, 받아들임 상태도 F = {r0}. 빈 문자열 ε도 1의 개수가 0이므로 받아들여진다. 단 세 개의 상태로 이론상 임의로 긴 입력의 1을 “3으로 나눈 나머지” 정보를 정확히 유지한다는 점이 인상적이다. 유한한 메모리가 무한한 입력 위에서 어떤 식으로 정보를 압축해 끌고 가는지를 잘 보여 준다.

4. 정규 언어

이렇게 만든 모델로 표현 가능한 언어들에 이름을 붙여 두자. 이 클래스가 앞으로 몇 강의 동안 우리의 주된 무대가 된다.

정의. 어떤 DFA M이 존재하여 L = L(M)이면, L을 정규 언어(regular language)라 한다.

정의를 보고 “DFA로만 정의되는 클래스인데 왜 이름을 따로 짓는가” 하는 의문이 들 수 있다. 그 답은 다음 두 강의에 걸쳐 자연스럽게 드러난다. 같은 클래스가 비결정적 모델로도, 정규 표현식으로도, 닫힘 연산의 결과로도 등장한다. 같은 산을 동·서·남쪽에서 각각 올라가 모두 같은 정상에 닿는 셈이다.

5. 정규 표현식

이제 같은 정상에 가는 또 다른 등산로를 살짝 엿본다. 정규 표현식(regular expression)은 언어를 구문론적으로, 즉 작은 표현식을 결합해 서서히 키우는 방식으로 정의한다.

정의. 알파벳 Σ 위의 정규 표현식(regex)은 다음 규칙으로 귀납적으로 정의된다.
  1. ∅은 정규 표현식이고, L(∅) = ∅.
  2. ε은 정규 표현식이고, L(ε) = {ε}.
  3. a ∈ Σ에 대해 a는 정규 표현식이고, L(a) = {a}.
  4. R1, R2가 정규 표현식이면 (R1 ∪ R2)도 정규 표현식이고, L(R1 ∪ R2) = L(R1) ∪ L(R2).
  5. (R1R2)도 정규 표현식이고, L(R1R2) = {xy : x ∈ L(R1), y ∈ L(R2)}.
  6. (R1*)도 정규 표현식이고, L(R1*) = {x1x2⋯xk : k ≥ 0, xi ∈ L(R1)}. 특히 ε ∈ L(R*) (k=0인 경우).

합집합 ∪, 연결(concatenation), 그리고 클레이니 스타(Kleene star) *—이 셋이 정규 표현식의 세 가지 기본 연산이다. 같은 표현식이라도 괄호와 우선순위 약속에 따라 외양이 달라진다. 통상적으로 *가 가장 강하게 결합하고, 그 다음이 연결, 마지막이 ∪이다.

예제. Σ = {0, 1}에서
  • (0 ∪ 1)*: 모든 이진 문자열의 집합 Σ*.
  • (0 ∪ 1)*1: 1로 끝나는 이진 문자열들.
  • 0*10*10*: 정확히 두 개의 1을 포함하는 이진 문자열들.
  • (00)*: 짝수 길이의 0-반복 문자열들 {ε, 00, 0000, ⋯}.
  • ∅*: 정의에 따라 {ε}이다. 공집합을 0번 이어 붙인 결과는 빈 문자열이라는 묘한 사실이다.
한 줄 메모. ∅과 ε은 흔히 헷갈린다. ∅은 “문자열이 하나도 없는 언어”, ε은 “길이 0짜리 문자열을 단 하나 가진 언어 {ε}”. 비유하자면 ∅은 빈 봉투조차 없는 상태이고, ε은 빈 봉투 하나가 들어 있는 상자다.

6. 다음 강의 예고

여기까지 우리는 결정적 기계와 구문적 표현식이라는 두 갈래 길을 깔아 두었다. 다음 강의에서는 길을 하나 더 추가한다. 한 상태에서 동시에 여러 곳으로 갈라질 수 있는 비결정적 유한 오토마타(NFA)가 그것이다. 처음에는 “편법 같다”는 느낌이 들겠지만, 놀랍게도 NFA가 인식할 수 있는 언어 클래스는 DFA의 그것과 정확히 같다는 사실을 증명할 것이다. 거기에 정규 표현식까지 같은 클래스로 합류하면, 정규 언어라는 한 봉우리에 세 개의 등산로가 모두 닿게 된다.