오토마타와 정규 언어

상태와 입력만으로 동작하는 가장 단순한 계산 모델인 유한 오토마타를 직접 만들어요. 2진수가 3의 배수인지 나머지 세 가지만 기억해 판별하는 DFA, 잘못된 순서를 막는 주문 상태 기계, 여러 갈래를 동시에 따라가는 NFA와 그것을 DFA로 바꿀 때 상태가 2ⁿ개로 불어나는 모습을 확인해요. 정규 표현식과 오토마타가 같은 언어를 다룬다는 것, 상태가 유한해서 괄호 짝이나 aⁿbⁿ을 셀 수 없다는 한계, 역추적 엔진에서 글자 몇 개에 시간이 폭발하는 정규 표현식까지 다뤄요.

고급강의 2 / 5약 14분

지난 강의의 래치는 "지금 상태"와 "들어온 입력"으로 다음 상태를 정했어요. 계산을 이렇게 바라보는 가장 단순한 모델이 유한 오토마타예요. 단순하지만 문자열 검사, 정규 표현식, 컴파일러의 첫 단계, 네트워크 프로토콜, 주문 처리 같은 곳에 그대로 쓰여요. 그리고 "단순한 기계로는 무엇을 할 수 없는가"를 처음으로 정확히 따져 볼 수 있는 모델이기도 해요. 이 트랙 전체의 질문인 "계산은 어디까지 가능한가"의 첫걸음이에요.

상태와 입력만으로 계산하기

유한 오토마타 중 가장 기본인 DFA(결정적 유한 오토마타)는 다섯 가지로 정해져요.

  • 상태의 집합(유한 개)
  • 입력 글자의 집합(알파벳)
  • 전이: (지금 상태, 읽은 글자)에서 다음 상태로
  • 시작 상태
  • 받아들이는 상태의 집합

입력을 한 글자씩 읽으며 상태를 옮기다가, 다 읽었을 때 받아들이는 상태에 있으면 "예", 아니면 "아니요"예요. 기억이라고는 지금 어느 상태인가 하나뿐이에요. 2진수가 3의 배수인지 판별하는 DFA를 만들어 볼게요.

class DFA:
    def __init__(self, transitions, start, accepting):
        self.transitions, self.start, self.accepting = transitions, start, accepting

    def run(self, text):
        state, path = self.start, [self.start]
        for ch in text:
            state = self.transitions.get((state, ch))
            if state is None:                            # 갈 곳이 정해져 있지 않으면 바로 거절
                return False, path
            path.append(state)
        return state in self.accepting, path

# 2진수를 왼쪽부터 읽으며 "지금까지 읽은 수를 3으로 나눈 나머지"만 기억해요
mod3 = DFA(
    transitions={(r, b): (2 * r + int(b)) % 3 for r in range(3) for b in "01"},
    start=0,
    accepting={0},
)
for bits in ["1100", "1011"]:
    ok, path = mod3.run(bits)
    print(f"{bits}({int(bits, 2)}): 3의 배수? {ok} | 지나간 상태 {path}")
print("0부터 4,095까지 모두 맞나요?", all(mod3.run(bin(n)[2:])[0] == (n % 3 == 0) for n in range(4096)))
1100(12): 3의 배수? True | 지나간 상태 [0, 1, 0, 0, 0]
1011(11): 3의 배수? False | 지나간 상태 [0, 1, 2, 2, 2]
0부터 4,095까지 모두 맞나요? True

수가 아무리 길어도 이 기계는 "지금까지 읽은 수를 3으로 나눈 나머지" 하나만 기억해요. 지금까지 읽은 수의 나머지가 r이고 다음 비트가 b면, 새 수는 2배에 b를 더한 값이니 새 나머지는 (2r + b)를 3으로 나눈 나머지예요. 상태 세 개로 끝없이 긴 수를 판별하는 셈이에요. DFA가 받아들이는 문자열들의 집합을 그 DFA가 인식하는 언어라고 하고, 어떤 DFA로 인식할 수 있는 언어를 정규 언어라고 해요.

상태 기계는 실무 곳곳에

오토마타는 이론만의 이야기가 아니에요. 주문, 결제, 회원 가입처럼 정해진 단계를 밟는 일은 상태 기계로 만들면 잘못된 순서를 원천적으로 막을 수 있어요.

ORDER = {                                                # (지금 상태, 일어난 일)에서 다음 상태로
    ("결제 대기", "결제"): "결제 완료",
    ("결제 대기", "취소"): "취소됨",
    ("결제 완료", "발송"): "배송 중",
    ("결제 완료", "취소"): "환불 중",
    ("배송 중", "도착"): "배송 완료",
    ("환불 중", "환불"): "취소됨",
}

def apply(events, state="결제 대기"):
    for event in events:
        nxt = ORDER.get((state, event))
        if nxt is None:
            return f"거절: '{state}' 상태에서는 '{event}'를 할 수 없어요"
        state = nxt
    return state

print(apply(["결제", "발송", "도착"]))
print(apply(["결제", "취소", "환불"]))
print(apply(["결제", "발송", "취소"]))
배송 완료
취소됨
거절: '배송 중' 상태에서는 '취소'를 할 수 없어요

허락된 전이를 표 하나에 모아 두니, "배송 중인 주문을 그냥 취소"처럼 업무 규칙에 없는 일은 코드 어디서 시도하든 거절돼요. 상태를 참과 거짓 변수 여러 개로 흩어 관리하면 "결제는 안 됐는데 배송 중" 같은 말이 안 되는 조합이 생기기 쉬워요. 네트워크 트랙에서 본 TCP의 LISTEN, ESTABLISHED, TIME_WAIT도 이런 상태 기계의 상태 이름이에요. 연결을 맺고, 주고받고, 닫는 단계마다 받을 수 있는 신호가 정해져 있어요.

비결정적 오토마타: 여러 갈래를 동시에

DFA는 상태와 글자가 정해지면 다음 상태가 딱 하나예요. 이 조건을 풀어서 다음 상태가 여러 개일 수 있게 한 것이 NFA(비결정적 유한 오토마타)예요. 갈림길에서 모든 갈래를 동시에 따라가고, 그중 하나라도 받아들이는 상태에 닿으면 "예"라고 생각하면 돼요.

"끝에서 n번째 글자가 1인가"는 NFA로 쉽게 표현돼요. 1을 볼 때마다 "이게 그 글자일지도 몰라" 하며 갈래를 하나 더 만들고, 거기서 n - 1글자를 더 읽었을 때 딱 입력이 끝나면 돼요.

def nfa_nth_from_end(n):                                 # "끝에서 n번째 글자가 1인가"를 보는 NFA
    moves = {}
    for ch in "01":
        moves[(0, ch)] = {0, 1} if ch == "1" else {0}    # 이 1이 바로 그 글자일지도 몰라요
        for i in range(1, n):
            moves[(i, ch)] = {i + 1}
    return moves, {n}

def step(moves, states, ch):                             # 갈 수 있는 곳을 모두 동시에 따라가요
    return frozenset().union(*(moves.get((s, ch), set()) for s in states))

def nfa_accepts(moves, accepting, text):
    current = frozenset({0})
    for ch in text:
        current = step(moves, current, ch)
    return bool(current & accepting)

def dfa_size(moves):                                     # 동시에 있을 수 있는 상태 묶음이 몇 가지인가
    seen, todo = {frozenset({0})}, [frozenset({0})]
    while todo:
        group = todo.pop()
        for ch in "01":
            nxt = step(moves, group, ch)
            if nxt not in seen:
                seen.add(nxt)
                todo.append(nxt)
    return len(seen)

moves, accepting = nfa_nth_from_end(3)
print("101100에서 끝에서 셋째 글자가 1인가요?", nfa_accepts(moves, accepting, "101100"))
print("101010은요?", nfa_accepts(moves, accepting, "101010"))
for n in range(1, 7):
    print(f"n={n}: NFA 상태 {n + 1}개 → 같은 일을 하는 DFA 상태 {dfa_size(nfa_nth_from_end(n)[0])}개")
101100에서 끝에서 셋째 글자가 1인가요? True
101010은요? False
n=1: NFA 상태 2개 → 같은 일을 하는 DFA 상태 2개
n=2: NFA 상태 3개 → 같은 일을 하는 DFA 상태 4개
n=3: NFA 상태 4개 → 같은 일을 하는 DFA 상태 8개
n=4: NFA 상태 5개 → 같은 일을 하는 DFA 상태 16개
n=5: NFA 상태 6개 → 같은 일을 하는 DFA 상태 32개
n=6: NFA 상태 7개 → 같은 일을 하는 DFA 상태 64개

NFA를 흉내 낼 때 "지금 있을 수 있는 상태들의 묶음"을 들고 다녔어요. 이 묶음 하나를 DFA의 상태 하나로 보면, 어떤 NFA든 같은 일을 하는 DFA로 바꿀 수 있어요. 이걸 부분집합 구성이라고 해요. 그래서 NFA가 DFA보다 더 많은 언어를 인식하지는 못해요. 대신 크기가 문제예요. 끝에서 n번째 글자를 보려면 DFA는 마지막 n글자를 모두 기억해야 해서 상태가 2ⁿ개로 불어나요. NFA는 n + 1개면 되고요. 능력은 같아도 표현의 크기는 지수적으로 다를 수 있어요.

정규 표현식은 오토마타예요

정규 표현식은 정규 언어를 글로 적는 방법이에요. 기본 재료는 셋뿐이에요.

  • 이어 붙이기: ab는 a 다음에 b예요.
  • 고르기: a|b는 a 또는 b예요.
  • 반복: a*는 a를 0번 이상 반복해요.

[ab], +, ? 같은 문법은 이 셋을 줄여 쓴 거예요. 그리고 정규 표현식으로 적을 수 있는 언어와 유한 오토마타가 인식하는 언어는 정확히 같다는 사실이 증명돼 있어요(클레이니 정리). 정규 표현식은 NFA로, NFA는 DFA로 바꿀 수 있고, 그 반대도 돼요. "a로 시작하고 b로 끝나는 문자열"을 DFA와 정규 표현식으로 각각 만들어 비교해 볼게요.

import re
from itertools import product

starts_a_ends_b = DFA(
    transitions={("시작", "a"): "a로 끝남", ("a로 끝남", "a"): "a로 끝남", ("a로 끝남", "b"): "b로 끝남",
                 ("b로 끝남", "a"): "a로 끝남", ("b로 끝남", "b"): "b로 끝남"},
    start="시작",
    accepting={"b로 끝남"},
)
pattern = re.compile(r"a[ab]*b")
words = ["".join(p) for n in range(9) for p in product("ab", repeat=n)]
same = all(starts_a_ends_b.run(w)[0] == bool(pattern.fullmatch(w)) for w in words)
print(f"길이 8 이하 문자열 {len(words):,}개에서 DFA와 정규 표현식의 판정이 모두 같나요?", same)
길이 8 이하 문자열 511개에서 DFA와 정규 표현식의 판정이 모두 같나요? True

길이 8 이하의 문자열 511개에서 두 판정이 하나도 다르지 않았어요. 정규 표현식 엔진은 표현식을 이런 기계로 바꿔서 문자열을 검사해요. 컴파일러의 첫 단계인 어휘 분석(코드를 이름, 숫자, 기호 같은 토큰으로 자르기)도 토큰마다 정규 표현식을 정하고, 그걸 하나의 DFA로 합쳐서 코드를 한 번에 훑어요. 이건 컴파일러 강의에서 다시 만나요.

오토마타가 셀 수 없는 것

유한 오토마타의 힘은 유한한 기억에서 오고, 한계도 거기서 와요. a를 n개 쓰고 이어서 b를 n개 쓴 문자열(anbna^n b^n: ab, aabb, aaabbb, ...)만 받아들이는 DFA를 만들 수 있을까요? a를 몇 개 읽었는지 세야 하니, 셀 수 있는 만큼 상태를 늘려 볼게요.

def counting_dfa(limit):                                 # a를 limit개까지 세고, b가 오면 하나씩 지워요
    t = {}
    for i in range(limit + 1):
        if i < limit:
            t[(("a", i), "a")] = ("a", i + 1)
        if i > 0:
            t[(("a", i), "b")] = ("b", i - 1)
            t[(("b", i), "b")] = ("b", i - 1)
    return DFA(t, ("a", 0), {("a", 0), ("b", 0)})

small = counting_dfa(3)
print("aabb:", small.run("aabb")[0], "| aab:", small.run("aab")[0], "| abab:", small.run("abab")[0])
for limit in (3, 100):
    dfa = counting_dfa(limit)
    first_fail = next(n for n in range(1, 1000) if not dfa.run("a" * n + "b" * n)[0])
    print(f"{limit}까지 세는 DFA(상태 {2 * limit + 1}개): a와 b가 {first_fail}개씩일 때 처음 틀려요")
aabb: True | aab: False | abab: False
3까지 세는 DFA(상태 7개): a와 b가 4개씩일 때 처음 틀려요
100까지 세는 DFA(상태 201개): a와 b가 101개씩일 때 처음 틀려요

3까지 세는 기계는 aabb를 받아들이고 aab와 abab는 거절하지만, a와 b가 4개씩이면 틀려요. 100까지 세도 101개에서 무너져요. 상태를 얼마나 늘리든 마찬가지예요. 이유는 조합론 강의의 비둘기집 원리예요.

  • 상태가 k개인 DFA에 a를 0개, 1개, ..., k개 읽히면, k + 1가지 경우가 상태 k개에 들어가니 서로 다른 i개와 j개를 읽고 같은 상태에 놓이는 경우가 반드시 생겨요.
  • 같은 상태에서 b를 i개 읽으면 결과도 같아야 해요. 그런데 aibia^i b^i는 받아들여야 하고 ajbia^j b^i는 거절해야 하니, 둘 중 하나는 틀려요.

그래서 어떤 DFA로도, 따라서 어떤 정규 표현식으로도 이 언어는 인식할 수 없어요. 괄호의 짝을 맞추는 것도 같은 이유로 불가능해요. 선형 구조 강의에서 괄호 짝을 맞출 때 스택을 썼죠. 끝없이 쌓을 수 있는 스택이 바로 유한한 상태에는 없는 능력이에요. "정규 표현식으로 HTML을 제대로 파싱할 수 없다"는 유명한 말도 여기서 나와요. 태그가 얼마든지 깊이 중첩될 수 있으니까요. 파이썬의 re에는 역참조처럼 정규 언어를 넘는 기능도 있지만, 임의로 깊은 중첩은 여전히 다루지 못해요. 중첩을 다루는 문법은 다음 강의에서 배워요.

정규 표현식이 느려지는 순간

이론상 정규 표현식은 DFA로 바꿔서 입력 길이에 비례하는 시간에 검사할 수 있어요. 그런데 파이썬, 자바스크립트, 자바 같은 많은 언어의 엔진은 DFA를 만들지 않고, 갈림길마다 하나를 골라 가 보다가 막히면 되돌아오는 역추적 방식을 써요. 역참조 같은 편리한 기능을 넣기 쉬워서예요. 대신 표현식에 따라 되돌아갈 갈림길이 폭발할 수 있어요.

import time

def seconds(pattern, text):
    start = time.perf_counter()
    re.match(pattern, text)
    return time.perf_counter() - start

t = {n: seconds(r"(a+)+$", "a" * n + "!") for n in (20, 22, 24)}
print("글자를 2개 늘릴 때마다 시간이 두 배 넘게 늘어나나요?", t[22] / t[20] > 2 and t[24] / t[22] > 2)
print("같은 뜻인 a+$는 1만 글자도 금방 끝나나요?", seconds(r"a+$", "a" * 10_000 + "!") < 0.1)
글자를 2개 늘릴 때마다 시간이 두 배 넘게 늘어나나요? True
같은 뜻인 a+$는 1만 글자도 금방 끝나나요? True

(a+)+$는 "a를 한 번 이상 반복한 덩어리"를 다시 반복하라는 뜻이라, a가 n개면 그걸 덩어리로 나누는 방법이 2의 (n - 1)제곱가지예요. 끝에 !가 있어서 결국 실패하는데, 엔진은 실패를 확인하려고 그 나눔을 하나하나 다 시도해요. 실제로 재 보면 글자가 2개 늘 때마다 시간이 4배쯤 늘어서, 이 컴퓨터 기준으로 어림하면 30글자에 1분 가까이, 40글자면 반나절이 걸려요. 뜻이 같은 a+$는 1만 글자도 바로 끝나요.

이런 공격을 ReDoS(정규 표현식 서비스 거부)라고 해요. 사용자가 보낸 문자열을 이런 표현식으로 검사하는 서버는 요청 몇 개로 CPU를 다 써 버릴 수 있어요. 2019년 클라우드플레어의 전 세계 장애도, 새로 배포한 정규 표현식 하나가 역추적 폭발을 일으켜 CPU를 가득 채운 데서 시작됐어요. 막는 방법은 이래요.

  • 반복 안에 반복을 넣는 것처럼, 같은 문자열을 여러 방법으로 나눌 수 있는 표현식을 피해요.
  • 사용자 입력에는 길이 제한부터 걸어요.
  • 파이썬 3.11부터는 되돌아가지 않게 막는 문법((?>...), a++)을 쓸 수 있어요.
  • 구글의 RE2나 Go와 Rust의 정규 표현식처럼, 오토마타 방식으로 입력 길이에 비례하는 시간을 보장하는 엔진을 써요. 대신 역참조 같은 기능은 없어요.

실습

  1. 2진수가 5의 배수인지 판별하는 DFA를 mod3처럼 만들고 0부터 4,095까지 확인해 보세요.
  2. 주문 상태 기계에 "배송 완료 후 반품 신청과 회수, 환불" 단계를 더해 보세요. 어떤 상태와 전이가 필요할까요?
  3. "a가 짝수 개이고 b가 홀수 개인 문자열"을 인식하는 DFA를 만들어 보세요. 상태는 몇 개가 필요할까요?
  4. nfa_nth_from_end(3)을 부분집합 구성으로 바꾼 DFA의 상태 묶음 8개가 각각 무엇을 기억하는지 설명해 보세요.
  5. (a|aa)+$와 (a|a)+$도 느려지는지 재 보고, 같은 뜻의 빠른 표현식으로 고쳐 보세요.

자주 하는 오해

  • 정규 표현식으로 무엇이든 검사할 수 있다. 괄호 짝이나 중첩 구조처럼 끝없이 세야 하는 것은 원리적으로 안 돼요.
  • NFA가 DFA보다 강하다. 인식할 수 있는 언어는 같아요. 표현이 더 짧을 수 있을 뿐이에요.
  • 정규 표현식은 늘 빠르다. 역추적 엔진에서는 표현식에 따라 입력 몇 글자에 시간이 폭발해요.
  • 상태 기계는 이론에만 있다. 주문 처리, 통신 규약, 게임 캐릭터, 화면 흐름처럼 단계가 있는 곳마다 있어요.
  • 이메일 주소를 정규 표현식 하나로 완벽하게 검사할 수 있다. 표준 규칙이 매우 복잡해서, 실무에서는 간단히 확인한 뒤 실제로 메일을 보내 확인해요.

점검 문제

  1. DFA를 정하는 다섯 가지는?
  2. 3의 배수를 판별하는 DFA가 상태 세 개로 끝없이 긴 수를 판별할 수 있는 이유는?
  3. 주문 상태를 상태 기계로 관리하면 좋은 점은?
  4. NFA는 어떻게 동작하고, DFA로 바꿀 수 있는 이유는?
  5. 끝에서 n번째 글자를 보는 DFA가 상태를 2ⁿ개나 필요로 하는 이유는?
  6. 정규 표현식과 유한 오토마타는 어떤 관계인가요?
  7. a를 n개 쓰고 b를 n개 쓴 문자열을 DFA로 인식할 수 없는 이유는?
  8. (a+)+$ 같은 정규 표현식이 위험한 이유와 막는 방법은?

정답

  1. 상태의 유한 집합, 입력 글자의 집합, (상태, 글자)에서 다음 상태를 정하는 전이, 시작 상태, 받아들이는 상태의 집합이에요.
  2. 판별에 필요한 정보가 "지금까지 읽은 수를 3으로 나눈 나머지" 하나뿐이기 때문이에요. 다음 비트 b를 읽으면 새 나머지는 (2r + b)를 3으로 나눈 나머지라, 나머지만 알면 계속 갱신할 수 있어요.
  3. 허락된 전이를 한곳에 모아 두니, 업무 규칙에 없는 순서는 어디서든 거절되고 말이 안 되는 상태 조합이 생기지 않아요.
  4. 다음 상태가 여러 개일 수 있어서 모든 갈래를 동시에 따라가고, 하나라도 받아들이는 상태에 닿으면 받아들여요. "지금 있을 수 있는 상태들의 묶음"을 DFA의 상태 하나로 보면 같은 일을 하는 DFA가 돼요.
  5. 입력이 언제 끝날지 모르니 마지막 n글자를 모두 기억하고 있어야 하는데, n글자의 0과 1 조합이 2ⁿ가지이기 때문이에요.
  6. 정규 표현식으로 적을 수 있는 언어와 유한 오토마타가 인식하는 언어는 정확히 같아요. 서로 바꿀 수 있고, 엔진은 표현식을 오토마타로 바꿔 검사해요.
  7. 상태가 k개면 a를 0개부터 k개까지 읽는 k + 1가지 경우 중 둘이 같은 상태에 놓여요. 그 뒤 같은 수의 b를 읽으면 결과도 같아야 하는데, 하나는 받아들이고 하나는 거절해야 하니 모순이에요.
  8. 같은 문자열을 덩어리로 나누는 방법이 지수적으로 많아서, 역추적 엔진이 실패를 확인하려고 그걸 다 시도하기 때문이에요. 반복 안의 반복을 피하고, 입력 길이를 제한하고, 되돌아가지 않는 문법이나 선형 시간을 보장하는 엔진을 써요.

다음 강의

유한 오토마타는 괄호의 짝조차 맞추지 못했어요. 프로그래밍 언어는 괄호 안에 괄호, 식 안에 식이 끝없이 들어가니 더 강한 도구가 필요해요. 다음 강의에서는 이런 중첩 구조를 정의하는 문맥 자유 문법과, 문법에 따라 코드를 나무 모양으로 읽어 내는 파싱을 직접 만들어 봐요.