DFA→정규식 변환기 (상태 제거법)
상태·전이표를 넣으면 상태를 하나씩 지우며 정규식을 합성하는 상태 제거법 과정을 그대로 보여주고, 원래 DFA와 판정이 같은지 대조합니다.
「상태 글자 상태」를 한 줄에 하나씩. 글자는 한 글자. start:·accept: 로 시작·받아들이는 상태를 지정합니다. 상태 6개까지.
정규식
b*a(a|b)*
길이 8 이하 문자열 511개에서 원래 DFA와 판정이 모두 같습니다.
상태 제거 — 회차마다 하나씩
지운 상태에 자기 자신으로 돌아오는 전이가 있었다면 그 부분에 *를 붙여, 몇 번이든 반복하고 지나갈 수 있게 압축합니다. 마지막 회차에 남는 하나의 식이 정규식입니다.
사용 방법
- 1전이를 「상태 글자 상태」 꼴로 한 줄에 하나씩 적습니다. 글자는 한 글자여야 합니다.
- 2「start: q0」으로 시작 상태를, 「accept: q1」로 받아들이는 상태(여럿이면 공백으로 나열)를 지정합니다.
- 3아래 상태 제거 회차마다 어떤 상태를 지웠고 남은 전이가 무엇인지 확인합니다.
- 4맨 끝에 남는 정규식이 결과이고, 원래 DFA와 짧은 문자열 전부에서 판정을 대조한 결과도 함께 보여줍니다.
자주 묻는 질문
전이에 정규식이 달린 오토마타(GNFA)로 바꾼 뒤, 시작·받아들이는 상태가 아닌 상태를 하나씩 지우면서 그 상태를 거쳐 가던 길을 하나의 정규식으로 압축하는 방법입니다. 상태가 시작·받아들이는 상태 둘만 남을 때까지 반복하면 그 사이에 남는 정규식이 답입니다. 모든 정규언어가 정규식으로 나타낼 수 있다는 정리의 증명이 곧 이 알고리즘입니다.
그 루프를 몇 번이든 반복할 수 있어야 하므로 정규식에 `*`(클리니 스타)를 붙입니다. p → q → r로 가는 길은 「p에서 q로 가는 식 · q의 루프(있으면) · q에서 r로 가는 식」을 이어 붙인 것이 되고, 이미 p → r로 가는 다른 길이 있었다면 |로 합칩니다.
나오는 언어(받아들이는 문자열의 집합)는 순서와 상관없이 항상 같지만, 정규식의 겉모양(길이·괄호 구조)은 지우는 순서마다 다를 수 있습니다. 이 계산기는 상태 이름의 사전순으로 지웁니다.
됩니다. DFA의 형식적 정의는 모든 상태·모든 글자에 전이가 있어야 하지만, 빠진 전이는 「그 글자로는 갈 곳이 없다」로 처리해도 받아들이는 언어는 똑같습니다 — 죽은 함정 상태를 그려 넣으나 생략하나 그 상태에서는 다시 받아들이는 곳으로 돌아올 수 없기 때문입니다.
길이 8 이하(글자 수가 많으면 더 짧게) 모든 문자열을 원래 DFA와 계산된 정규식에 각각 넣어 판정이 같은지 대조합니다. 화면에 몇 개를 대조했는지, 어긋난 문자열이 있는지 그대로 나옵니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- Sipser 「계산 이론(Introduction to the Theory of Computation)」 1.3절 — 「모든 정규언어는 어떤 정규식과도 대응된다」의 증명(GNFA로의 변환과 상태 제거)을 그대로 구현했습니다.
- 검증은 원래 DFA를 직접 굴린 결과와, 상태 제거로 얻은 정규식을 문자열에 대조한 결과를 길이 8 이하 모든 문자열에서 맞대보는 방식입니다. 이 대조는 계산기 화면에서도 그대로 돌아갑니다.
- 「a가 적어도 하나」·「a 개수가 짝수」 같은 잘 알려진 언어의 DFA는 자바스크립트 내장 정규식(RegExp)으로도 이중 대조해, 상태 제거 결과가 그 언어의 정의와 정확히 같은 문자열을 받아들이는지 테스트로 확인했습니다.
- 상태 6개·글자 4개까지 다룹니다. 상태 제거법은 지울 때마다 정규식이 길어질 수 있어(최악의 경우 상태 수에 지수적으로) 그보다 커지면 정규식이 화면에 담기 어렵습니다.
- 같은 글자로 가는 전이가 두 개면(예: q0에서 a로 q1과 q2 둘 다) 결정성 위반으로 에러가 됩니다. NFA가 아니라 DFA만 다룹니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.