NFA에서 최소 DFA까지: 정규식이 실행 가능한 오토마타가 되는 과정

이 글은 개인 학습 아카이브에 보관된 컴파일러 강의 PDF·슬라이드·코드 예제를 교차 검토해 새로 구성한 학습 노트입니다. 오래된 표기, 오탈자, 실행되지 않는 예시는 본문에서 별도로 바로잡았으며 원본 파일이나 내부 경로는 공개하지 않습니다.

결정적이라는 말의 의미

DFA에서는 현재 state와 다음 입력 기호가 주어지면 next state가 정확히 하나다.

δ_DFA: Q × Σ → Q

NFA에서는 같은 조건에서 가능한 next state가 0개, 1개, 또는 여러 개일 수 있다.

δ_NFA: Q × Σ → 2^Q

ε-NFA는 입력을 소비하지 않는 ε transition까지 허용한다. 표현 방식이 더 자유로울 뿐, NFA·ε-NFA·DFA가 인식하는 언어의 범위는 모두 regular language로 같다.

NFA를 “경로 열거”가 아니라 상태 집합으로 실행하기

NFA가 입력 a를 읽고 q1과 q2 두 곳으로 갈 수 있다고 해서 실제 구현이 실행 스레드를 무조건 둘로 복제해야 하는 것은 아니다. 현재 가능한 상태를 set으로 유지하면 된다.

current = {start}
for symbol in input:
  next = ∅
  for state in current:
    next = next ∪ δ(state, symbol)
  current = next
accept if current intersects F

naive하게 모든 recognition path를 재귀 열거하면 지수적으로 늘 수 있다. 그러나 상태 집합 simulation은 각 입력 위치에서 가능한 상태를 합치므로 대략 입력 길이와 transition 수에 비례한다. 지수 폭발의 핵심 위치는 NFA 실행 자체가 아니라 모든 상태 부분집합을 미리 DFA state로 materialize하는 subset construction의 최악 경우다.

ε-closure

ε-NFA에서는 입력을 읽기 전과 읽은 뒤에 공짜 이동을 모두 따라가야 한다.

• ε-closure(S): S에서 ε transition만 0회 이상 따라 도달할 수 있는 상태 집합
• move(S, a): S의 각 state에서 a transition으로 한 번 이동한 합집합

실행 한 단계는 다음과 같다.

current = ε-closure({start})
for symbol in input:
  current = ε-closure(move(current, symbol))

closure는 출발 state 자신도 포함한다. cycle이 있을 수 있으므로 visited set 없이 재귀하면 끝나지 않는다.

subset construction: NFA state 집합을 DFA state로

NFA를 DFA로 바꾸는 핵심 아이디어는 “NFA가 동시에 있을 수 있는 상태 집합 하나”를 “DFA state 하나”로 보는 것이다.

1. DFA start state는 ε-closure({NFA start})다.
2. 아직 처리하지 않은 DFA state-set S와 각 symbol a에 대해 ε-closure(move(S,a))를 계산한다.
3. 처음 본 집합이면 새 DFA state로 등록한다.
4. NFA accepting state를 하나라도 포함한 집합은 DFA에서도 accepting이다.

power set에는 빈 집합 ∅도 포함된다. 어떤 symbol로도 갈 곳이 없는 경우 ∅는 모든 symbol에서 자신으로 가는 sink state가 된다. 그림을 간단히 하려고 sink를 생략할 수는 있지만, complement나 완전 transition table을 만들 때는 다시 넣어야 한다.

NFA state가 n개면 이론상 DFA state는 최대 2ⁿ개다. 실제 변환은 start에서 도달 가능한 subset만 생성하므로 훨씬 적을 수 있다.

Thompson construction: 정규식을 ε-NFA로

복잡한 정규식을 작은 조각으로 조합한다.

• symbol a: start에서 accept로 가는 a transition
• union r|s: 새 start가 ε로 두 조각에 갈라지고 두 accept가 새 accept로 합쳐짐
• concatenation rs: r의 accept를 ε로 s의 start에 연결
• star r*: 빈 문자열 경로와 반복 경로를 ε transition으로 추가

예를 들어 (a|b)*a는 a와 b의 union 조각을 star로 감싼 뒤 마지막 a 조각을 연결한다. 강의 자료의 한 예제에는 union을 의도한 위치가 concatenation ab처럼 적힌 오탈자와, union을 +로 쓰는 오래된 표기가 섞여 있다. 여기서는 현대적인 | 표기로 의미를 분리한다.

Thompson NFA는 state가 많고 ε transition이 있지만 구성 규칙이 국소적이라 parser가 만든 regex syntax tree에서 기계적으로 생성하기 쉽다.

DFA 최소화

subset construction의 DFA에는 서로 구분할 수 없는 state가 있을 수 있다. 두 state가 앞으로 어떤 suffix를 붙여도 항상 같은 acceptance 결과를 낸다면 equivalent하다. partition refinement는 이를 찾는다.

1. 먼저 accepting state와 non-accepting state를 두 partition으로 나눈다.
2. 같은 partition 안에서도 어떤 symbol의 destination partition이 다르면 분리한다.
3. 더 이상 partition이 바뀌지 않을 때까지 반복한다.
4. 각 partition을 최소 DFA의 state 하나로 합친다.

시작점에서 도달 불가능한 state는 먼저 제거해야 한다. 완전 DFA를 원하면 sink도 포함해 최소화한다. 결과는 state 이름의 차이를 제외하면 유일한 최소 DFA다.

작은 구분 예제

“마지막 두 문자가 01인 이진 문자열”을 인식한다고 하자. state는 필요한 suffix 정보만 기억한다.

• A: 유용한 suffix 없음
• B: 마지막 문자가 0
• C: 마지막 두 문자가 01, accepting

C에서 다음 symbol을 읽으면 acceptance는 새 suffix에 따라 다시 달라진다. accepting state가 한 번 되었다고 영원히 accepting인 것은 “00을 한 번이라도 포함” 같은 언어에서만 맞다. state의 의미를 자연어 invariant로 먼저 적으면 전이표 오류를 빠르게 찾을 수 있다.

정규 언어의 닫힘 성질

두 DFA의 상태를 (q1,q2) 쌍으로 묶는 product construction을 이용하면:

• union: 둘 중 하나가 accepting이면 accepting
• intersection: 둘 다 accepting이면 accepting
• difference: 첫째는 accepting이고 둘째는 아니면 accepting

concatenation과 star는 ε-NFA 조합으로 자연스럽게 만들 수 있다. “닫혀 있다”는 말은 연산 결과도 regular라는 존재 주장에 그치지 않고 실제 automaton을 만드는 알고리즘까지 준다.

구현 체크리스트

• NFA transition의 반환형은 state 하나가 아니라 set이다.
• ε-closure는 입력 전과 각 move 뒤에 적용한다.
• visited set으로 ε cycle을 막는다.
• subset key는 정렬된 immutable state 집합처럼 canonical하게 만든다.
• ∅와 sink 생략 여부를 명시한다.
• DFA accept 여부는 subset이 F와 교집합을 갖는지로 정한다.
• 최소화 전에 unreachable state를 제거한다.
• 원본 NFA simulation과 변환된 DFA를 같은 문자열 묶음으로 property test한다.

정규식에서 빠른 scanner로 가는 길은 “마법의 변환”이 아니다. 조합하기 쉬운 ε-NFA, 실행 상태를 고정한 DFA, 중복 미래를 합친 최소 DFA라는 세 표현 사이에서 목적에 맞게 비용을 이동하는 과정이다.