정규 표현식과 유한 상태 오토마타 (Regex / DFA)

정규 표현식과 유한 상태 오토마타

^\d{3}-\d{4}$ 같은 정규식(regular expression)은 사실 아주 작은 기계다. 문자를 하나씩 읽으며 상태(state)를 갈아타다가, 문자열이 끝났을 때 "받아들이는 상태"에 있으면 매치 성공. 이 기계를 유한 상태 오토마타(Finite Automaton)라고 부른다. 아래에서 치트시트 · 라이브 테스터 · 상태 기계 시뮬레이터 · 파괴적 백트래킹(ReDoS)까지 직접 만져보자.

1. 메타문자 치트시트

정규식은 "그대로 매치되는 글자" + "특별한 뜻을 가진 메타문자"의 조합이다.

기호	의미	예시
.	줄바꿈을 제외한 아무 글자 1개	`a.c` → "abc", "a-c"
*	바로 앞 요소를 0번 이상 반복	`ab*` → "a", "ab", "abbb"
+	바로 앞 요소를 1번 이상 반복	`ab+` → "ab", "abbb" (X: "a")
?	바로 앞 요소가 0번 또는 1번 (선택)	`colou?r` → "color", "colour"
{n,m}	n번 이상 m번 이하 반복	`\d{2,4}` → "12", "1234"
[ ]	문자 클래스 — 괄호 안 글자 중 하나	`[aeiou]`, `[a-z0-9]`
[^ ]	부정 문자 클래스 — 괄호 안 글자만 빼고	`[^0-9]` → 숫자가 아닌 글자
\|	선택(OR)	`cat\|dog` → "cat" 또는 "dog"
( )	그룹 — 묶어서 반복하거나 캡처	`(ab)+` → "ab", "ababab"
^ $	문자열의 시작 / 끝 (앵커)	`^hi$` → 정확히 "hi"
\d \w \s	숫자 / 단어문자([A-Za-z0-9_]) / 공백	`\w+@\w+`
\b	단어 경계 (글자와 비글자 사이)	`\bcat\b` → "the cat" O, "category" X

2. 라이브 정규식 테스터

브라우저 내장 RegExp 엔진으로 즉석에서 돌려본다. 매치 구간이 보라색으로 칠해지고, 캡처 그룹도 표시된다.

정규식 (슬래시 없이 패턴만)

플래그

테스트 문자열

3. 상태 기계 시뮬레이터 — "3으로 나누어떨어지는 2진수"

정규 언어의 고전 예제. 상태는 "지금까지 읽은 값을 3으로 나눈 나머지"(0·1·2)를 뜻한다. 비트를 하나 읽을 때마다 값은 2·현재값 + 새비트가 되므로 나머지도 규칙적으로 바뀐다. 문자열이 끝났을 때 나머지가 0(이중 원 = 수락 상태)이면 3의 배수다.

2진수 입력

상태 q0 · 읽은 값 0 · 나머지 0

판정: 대기 중

전이표 δ:
q0 —0→ q0, q0 —1→ q1
q1 —0→ q2, q1 —1→ q0
q2 —0→ q1, q2 —1→ q2
이 기계에는 스택도, 카운터도 없다. 오직 3개의 상태로 "무한히 긴" 2진수도 검사할 수 있다.

4. 정규식은 어떻게 기계가 되나

Thompson 구성법 → NFA → DFA 변환. 대부분의 검색 엔진(grep, RE2)이 이 길을 택한다.

① NFA (비결정적)
각 연산자(*, |, 이어붙이기)마다 정해진 작은 조각을 ε(빈) 화살표로 이어 붙인다. 한 글자에 갈 수 있는 상태가 여러 개일 수 있다.

② DFA (결정적)
"지금 가능한 NFA 상태들의 집합"을 하나의 DFA 상태로 묶는다(부분집합 구성). 그러면 글자마다 갈 곳이 딱 하나 → 입력 길이에 정확히 비례하는 O(n) 시간에 매치.

# 파이썬 표준 재귀 매처 (백트래킹식)
def match(re, s):
    if re == "":            # 패턴 소진
        return s == ""
    if len(re) > 1 and re[1] == "*":
        # 0번 쓰거나 / 1번 쓰고 다시 시도
        return match(re[2:], s) or (
            s and (re[0] in (s[0], "."))
            and match(re, s[1:]))
    if s and (re[0] in (s[0], ".")):
        return match(re[1:], s[1:])
    return False

왜 두 갈래로 나뉘나? DFA 방식은 항상 빠르지만 역참조(\1)·전방탐색 같은 확장 기능을 못 쓴다. Python·JavaScript·PCRE는 기능이 풍부한 백트래킹 엔진을 쓰는데, 그 대가가 바로 아래의 함정이다.

5. 파괴적 백트래킹 (ReDoS)

(a+)+$ 처럼 반복 안에 반복이 겹친 패턴에, 매치에 실패하는 문자열(aaaa...!)을 주면 엔진이 "a를 이렇게 나눠볼까, 저렇게 나눠볼까"를 지수적으로 시도한다. 글자 하나 늘 때마다 시간이 약 2배.

패턴 'a' 개수 최대

방어법 ① 반복 중첩을 없앤다 → a+$ 로 충분. ② 원자 그룹 (?>a+)+ / 소유 수량자 a++ 로 백트래킹 금지. ③ 애초에 DFA 기반 엔진(Go regexp, Rust regex, RE2)을 쓴다. ④ 사용자 입력을 정규식으로 그대로 받지 않는다.

6. 한 장 정리

정규식 = 유한 상태 기계. 글자를 읽으며 상태를 옮기다 끝에서 수락 상태면 매치.
순수 정규식은 중첩된 괄호 짝 맞추기(예: HTML 완전 파싱) 같은 건 못 한다 — 그건 스택이 필요한 문법의 영역.
DFA 엔진: 항상 O(n), 기능 제한. 백트래킹 엔진: 기능 풍부, 최악엔 지수 시간.
실무에서는 앵커(^ $)를 붙이고, 반복 중첩을 피하고, 입력 길이를 제한하라.