정규 표현식의 내부 — NFA와 DFA로 패턴을 매칭하는 법

정규 표현식: ab*c

DFA:
  상태 0 --a--> 상태 1 --b--> 상태 1 (루프)
                       --c--> 상태 2 (수락)

정규 표현식: a|b

NFA:
  시작 --ε--> 상태 1 --a--> 수락
       --ε--> 상태 2 --b--> 수락

// Thompson NFA — 개념적 구현
public boolean thompsonMatch(String text) {
    Set<Integer> currentStates = epsilonClosure(Set.of(startState));

    for (char c : text.toCharArray()) {
        Set<Integer> nextStates = new HashSet<>();
        for (int state : currentStates) {
            // 현재 상태에서 c로 전이 가능한 모든 다음 상태
            nextStates.addAll(transition(state, c));
        }
        currentStates = epsilonClosure(nextStates);
    }

    return currentStates.contains(acceptState);
}

입력: "aaaaab"
패턴: (a+)+

백트래킹:
  "aaaaa" → 실패 → "aaaa" + "a" → 실패 → "aaa" + "aa" → ...
  → 분할 방법이 지수적으로 증가!

정규 표현식 → (Thompson 구성) → NFA → (부분집합 구성) → DFA → (최소화) → 최소 DFA

// 단일 문자: a
//   시작 --a--> 수락

// 연결: ab
//   NFA(a)의 수락 --ε--> NFA(b)의 시작

// 선택: a|b
//   새 시작 --ε--> NFA(a)의 시작
//          --ε--> NFA(b)의 시작
//   NFA(a)의 수락 --ε--> 새 수락
//   NFA(b)의 수락 --ε--> 새 수락

// 반복: a*
//   새 시작 --ε--> NFA(a)의 시작
//          --ε--> 새 수락
//   NFA(a)의 수락 --ε--> NFA(a)의 시작 (루프)
//                 --ε--> 새 수락

// NFA 상태 {0, 1, 3} → DFA 상태 A
// NFA 상태 {2, 4}    → DFA 상태 B
// ...

// 위험! 중첩 반복
Pattern.compile("^(a+)+$");       // "aaaaab"에 지수 시간
Pattern.compile("^(a|a)+$");      // 같은 문제
Pattern.compile("^(a+b?)+$");     // 마찬가지

"aaaaa" 분할 방법:
(aaaaa), (aaaa)(a), (aaa)(aa), (aaa)(a)(a), (aa)(aaa), ...
→ 2^(n-1) 가지

// 1. 중첩 반복 피하기
// Bad:  ^(a+)+$
// Good: ^a+$

// 2. 원자 그룹/독점적 수량자 사용 (Java)
Pattern.compile("^(?>a+)+$");  // 원자 그룹 — 백트래킹 방지

// 3. 타임아웃 설정
// Java에서는 별도 스레드로 실행하고 타임아웃 적용
ExecutorService executor = Executors.newSingleThreadExecutor();
Future<Boolean> future = executor.submit(() -> pattern.matcher(input).matches());
try {
    return future.get(100, TimeUnit.MILLISECONDS);
} catch (TimeoutException e) {
    future.cancel(true);
    return false;
}

// 4. 입력 길이 제한
if (input.length() > MAX_LENGTH) {
    throw new ValidationException("입력이 너무 깁니다");
}

// Java 정규 표현식 사용
Pattern pattern = Pattern.compile("\\d{4}-\\d{2}-\\d{2}");
Matcher matcher = pattern.matcher("2026-03-19");

if (matcher.matches()) {
    System.out.println("날짜 형식 맞음");
}

// 그룹 캡처
Pattern p = Pattern.compile("(\\w+)@(\\w+\\.\\w+)");
Matcher m = p.matcher("user@example.com");
if (m.matches()) {
    String user = m.group(1);   // "user"
    String domain = m.group(2); // "example.com"
}

// Bad — 매 호출마다 컴파일
public boolean validate(String input) {
    return input.matches("\\d+"); // 내부에서 매번 Pattern.compile()
}

// Good — 한 번 컴파일하고 재사용
private static final Pattern DIGIT_PATTERN = Pattern.compile("\\d+");

public boolean validate(String input) {
    return DIGIT_PATTERN.matcher(input).matches();
}

public class UserDto {
    @Pattern(regexp = "^[a-zA-Z0-9_]{3,20}$", message = "올바른 사용자명이 아닙니다")
    private String username;

    @Pattern(regexp = "^\\+?\\d{10,15}$", message = "올바른 전화번호가 아닙니다")
    private String phone;
}