톰슨 구성법 계산기 (정규식→NFA)
정규식을 연산자(연결·선택·*·+·?)마다 정해진 ε-NFA 조각으로 재귀적으로 이어붙여 NFA를 만듭니다. 조각별 구성 과정과 dev/nfa-dfa로 이어지는 nfa-dfa 입력 형식을 그대로 보여줍니다.
리터럴 문자·|·*·+·?·() 를 지원합니다. 40자까지.
만들어진 NFA
상태 14개
글자 a, b · 시작 q6 · 받아들이는 상태 q13
구성 과정 (바닥부터)
연산자마다 정해진 조각(기호는 상태 2개, 선택·별표는 새 시작·accept와 ε-전이 4개 …)을 재귀적으로 이어붙입니다. 마지막 줄이 전체 정규식의 시작·accept입니다.
nfa-dfa 입력 형식
start: q6 accept: q13 q0 a q1 q1 eps q5 q10 b q11 q11 eps q12 q12 b q13 q2 b q3 q3 eps q5 q4 eps q0 q4 eps q2 q5 eps q4 q5 eps q7 q6 eps q4 q6 eps q7 q7 eps q8 q8 a q9 q9 eps q10
그대로 복사해 dev/nfa-dfa에 붙여넣으면 부분집합 구성으로 DFA로 바꾸고 최소화까지 이어서 할 수 있습니다.
문자열 검사
사용 방법
- 1정규식을 입력합니다. 리터럴 문자·|(선택)·*(0번 이상)·+(1번 이상)·?(있어도 없어도)·괄호를 지원합니다.
- 2바닥(리터럴)부터 위로 조각이 이어붙는 구성 과정을 확인합니다.
- 3만들어진 NFA를 nfa-dfa 입력 형식으로 복사해 dev/nfa-dfa에 붙여넣으면 바로 DFA로 바꿀 수 있습니다.
- 4아래 검사기에 문자열을 넣어 이 정규식이 받아들이는지 직접 시험해 봅니다.
자주 묻는 질문
정규식의 각 연산자(리터럴·연결·선택·별표)마다 ε-전이가 있는 고정된 부분 NFA 조각을 대응시켜, 정규식을 아래에서 위로 훑으며 그 조각들을 재귀적으로 이어붙이는 절차입니다. 1968년 켄 톰슨이 발표했고, 정규식을 실제로 매칭 엔진으로 만드는 표준 방법 중 하나입니다.
조각을 독립적으로 만들고 ε-전이로만 이으면, 재귀호출 하나하나가 자기 완결적인 "시작 상태 하나·accept 상태 하나짜리 부분 NFA"라는 불변조건을 유지할 수 있습니다. 이 불변조건 덕분에 연결·선택·별표 규칙이 항상 똑같은 모양으로 적용되고, 구성 전체가 정규식의 구조에 대한 귀납으로 정확함을 증명할 수 있습니다. 상태를 재사용하면 이 불변조건이 깨집니다.
맞습니다. 원래 톰슨 구성법은 연결·선택·별표(*) 세 가지만 다룹니다. +(1번 이상)와 ?(있어도 없어도)는 e+ = ee*, e? = e|ε로 풀어 쓸 수 있는 파생 연산자입니다. 이 계산기는 새 상태를 하나 덜 쓰는 지름길 조각(+는 별표 조각의 시작을 그대로 재사용, ?는 별표에서 되돌아가는 ε-전이만 뺀 모양)으로 직접 구현했지만, 결과로 받아들이는 언어는 위 치환과 동일합니다.
이 계산기 자체 테스트에서 두 가지로 검증합니다. 하나는 만든 NFA로 문자열을 판정한 결과를 자바스크립트 내장 RegExp와 대조하는 것이고(지원하는 문법이 JS 정규식의 부분집합이라 같은 패턴을 그대로 넣을 수 있습니다), 다른 하나는 만든 NFA를 dev/nfa-dfa의 변환 함수에 그대로 먹여 NFA·DFA·최소화 DFA 세 판정이 일치하는지(그 도구 자체의 verified 검증) 보는 것입니다. 화면 아래 검사기로 직접 문자열을 넣어 볼 수도 있습니다.
정규식은 40자까지, 만들어지는 NFA 상태는 dev/nfa-dfa가 다루는 한도인 14개까지, 서로 다른 글자는 6개까지입니다. 이 한도를 넘으면 이유와 함께 거절합니다. 리터럴 문자 하나가 최소 2개 상태를 쓰므로 짧은 정규식으로도 금방 한도에 닿을 수 있습니다.
아니요. 정규식과 검사 문자열은 모두 브라우저에서만 계산되며 서버로 전송되지 않습니다.
알아두면 좋은 점
- 지원 문법: 리터럴 문자, 연결(이어쓰기), |(선택), *(0번 이상), +(1번 이상), ?(있어도 없어도), ()(묶기). 문자 클래스([a-z])·앵커(^$)·이스케이프는 다루지 않습니다.
- +와 ?는 표준 치환(e+ = ee*, e? = e|ε)과 같은 언어를 받아들이는 지름길 조각으로 직접 구현했습니다.
- 정규식은 40자, NFA 상태는 14개, 서로 다른 글자는 6개까지 다룹니다 — dev/nfa-dfa의 한도와 맞췄습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.