정규식을 DFA로 변환 (NFA, 부분집합 구성, 최소 DFA)
정규 표현식을 톰슨 NFA, 부분집합 구성법의 DFA, 최소 DFA로 변환하고 전이표를 보여 주며, 문자열의 수락·거부를 테스트합니다.
알파벳은 식에 쓰인 기호의 집합입니다: a, b.
최소 DFA의 상태 이름은 합쳐진 DFA 상태의 이름을 따릅니다. "—"는 없는 전이, 즉 입력이 거부됨을 뜻합니다.
| 상태 | ε | a | b |
|---|---|---|---|
| → 0 | {1,2} | — | — |
| 1 | {3,4} | — | — |
| 2 | — | {5} | — |
| 3 | — | {6} | — |
| 4 | — | — | {7} |
| 5 | — | — | {8} |
| 6 | {9} | — | — |
| 7 | {9} | — | — |
| 8 | — | — | {10} |
| 9 | {1,2} | — | — |
| * 10 | — | — | — |
| 상태 | NFA 상태 수 | a | b |
|---|---|---|---|
| → A | {0,1,2,3,4} | B | C |
| B | {1,2,3,4,5,6,9} | B | D |
| C | {1,2,3,4,7,9} | B | C |
| D | {1,2,3,4,7,8,9} | B | E |
| * E | {1,2,3,4,7,9,10} | B | C |
| 상태 | a | b |
|---|---|---|
| → AC | B | AC |
| B | B | D |
| D | B | E |
| * E | B | AC |
| 문자열 | 결과 | DFA 경로 |
|---|---|---|
| abb | 수락 | A → B → D → E |
| aabb | 수락 | A → B → B → D → E |
| babb | 수락 | A → C → B → D → E |
| ab | 거부 | A → B → D |
| abba | 거부 | A → B → D → E → B |
컴파일러와 오토마타 수업에서는 정규 표현식을 세 단계로 기계로 바꿉니다. 톰슨 구성으로 ε 이동이 있는 NFA를 만들고, 부분집합 구성으로 DFA로 바꾸고, 최소화로 같게 동작하는 상태를 합칩니다. 이 도구는 형식적 정규 표현식에 대해 세 단계를 모두 수행하고 각 기계의 전이표를 시작·수락 상태 표시와 함께 보여 준 뒤, 테스트 문자열을 최소 DFA에 넣어 각각이 지나는 경로를 보여 줍니다.
사용 방법
- |, *, +, ?, 괄호, ε(또는 eps)를 써서 정규 표현식을 입력합니다.
- +가 "1회 이상"인지, 일부 교재처럼 "또는"인지 정합니다.
- 테스트할 문자열을 한 줄에 하나씩 입력합니다(빈 줄은 빈 문자열 검사).
- NFA, DFA, 최소 DFA 표와 수락/거부 결과를 확인합니다.
계산식
DFA 상태 = NFA 상태 집합의 ε-폐포 · move(T, a) = T에서 a로 도달할 수 있는 NFA 상태 · 최소 DFA = 앞으로의 동작이 같은 상태들의 클래스
톰슨 구성은 기호마다 상태 둘을 만들고 |, *, +, ?마다 상태 둘을 더하며, 연결은 드래곤 북(Dragon Book)처럼 앞 부분의 끝과 다음 부분의 시작을 합칩니다. 부분집합 구성은 DFA 상태를 발견한 순서대로 A, B, C … 로 이름 붙입니다. 최소화는 수락/비수락 분할에서 시작해, 한 그룹의 상태가 모든 기호에서 같은 그룹으로 가게 될 때까지 나눕니다(무어 알고리즘, 홉크로프트 알고리즘과 결과가 같음). 죽은 상태는 없는 전이를 모으며 표시하거나 숨길 수 있습니다.
예시
(a|b)*abb에 대해 톰슨 구성은 NFA 상태 11개를 만듭니다. 부분집합 구성은 DFA 상태 A~E 5개를 만들고 전이는 드래곤 북의 표와 똑같으며, E만 수락 상태입니다. A와 C는 동작이 같으므로 최소 DFA는 AC, B, D, E의 상태 4개입니다. 테스트 문자열 중 abb, aabb, babb는 수락되고 ab와 abba는 거부됩니다.
자주 묻는 질문
DFA가 NFA보다 상태가 많을 수 있는 이유는 무엇인가요?
DFA 상태 하나는 NFA 상태의 집합 하나이고, 그런 집합은 최대 2ⁿ개일 수 있습니다. 보통은 도달 가능한 것이 몇 개뿐이지만 어떤 식은 정말로 지수적으로 많은 상태가 필요하며, 이 도구는 2,000개에서 멈춥니다.
프로그래밍 언어의 정규식과 같은가요?
아니요. 이것은 오토마타 이론의 형식적 표기로 합집합, 연결, 스타, 플러스, 선택만 있습니다. 역참조나 전방 탐색 같은 기능은 정규적이지 않아 DFA로 바꿀 수 없습니다.
죽은 상태란 무엇인가요?
모든 기호에서 자기 자신으로 돌아오는 비수락 상태로 "이 입력은 절대 수락될 수 없다"를 뜻합니다. 표에서는 흔히 생략하며, 옵션을 켜면 표시됩니다.
출처
최종 업데이트:
이 입력값이 담긴 페이지 주소: https://kakao.mobile/ko/tools/regex-to-dfa-tool/
인용·퍼가기
kakaoCalc. (2026, November 8). 정규식을 DFA로 변환 (NFA, 부분집합 구성, 최소 DFA). https://kakao.mobile/ko/tools/regex-to-dfa-tool/
“정규식을 DFA로 변환 (NFA, 부분집합 구성, 최소 DFA).” kakaoCalc, 8 Nov. 2026, kakao.mobile/ko/tools/regex-to-dfa-tool/.