DFA 최소화(호프크로프트) 계산기

마이힐–네로드 정리에 따르면, 같은 언어를 받아들이는 DFA 가운데 상태 수가 가장 적은 것은(상태 이름 붙이기 차이를 빼면) 유일합니다. 그래서 "최소화"는 상태를 임의로 지우는 것이 아니라, 서로 구별할 수 없는 상태들을 정확히 찾아 하나로 합치는 과정입니다.

그 상태에서 시작해 어떤 문자열을 이어 붙여도 두 상태 모두 항상 같은 결과(둘 다 수락하거나 둘 다 거부)를 낸다는 뜻입니다. 반대로 구별하는 문자열이 하나라도 있으면 두 상태는 합칠 수 없습니다.

시작 상태에서 갈 수 없는 상태는 언어에 아무 영향을 주지 않아 항상 서로 구별 불가능하게 뭉뚱그려지고, 그러면 최소화 결과가 실제보다 작거나 잘못된 방향으로 나올 수 있습니다. 그래서 분할 세련화를 돌리기 전에 반드시 도달 가능한 상태만 남겨야 합니다.

처음에는 수락 상태와 비수락 상태, 딱 두 덩어리로 나눕니다. 이후 매 라운드마다 "지금 같은 덩어리에 있고, 각 기호마다 간 곳도 같은 덩어리인" 상태들만 한 덩어리로 남기고 나머지는 쪼갭니다. 블록 개수가 이전 라운드와 같아지면(=아무도 안 쪼개지면) 멈춥니다.

길이 0부터 지정한 최대 길이까지의 모든 문자열을 실제로 넣어, 원래 DFA와 최소화한 DFA의 수락 여부가 항상 같은지 전수 확인합니다. 다르면 그 문자열을 반례로 보여 줍니다.

네, 다른 단계입니다. dev/nfa-dfa가 비결정적 오토마타(NFA)를 부분집합 구성법으로 결정적 오토마타(DFA)로 바꾸는 도구라면, 이 도구는 이미 DFA인 것을 더 작게(최소로) 만드는 다음 단계입니다.

호프크로프트가 제시한 O(n log n) 최적화(작은 쪽 블록만 골라 분할을 전파하는 방식)까지는 아니고, 그 바탕이 되는 분할 세련화(Moore식, O(n²·|Σ|))를 그대로 구현했습니다. 결과로 나오는 최소 DFA는 두 방식 모두 똑같습니다 — 차이는 속도뿐입니다. 이 계산기가 다루는 작은 DFA에서는 체감되지 않습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.