NFA→DFA 변환기 (부분집합 구성)

NFA가 지금 있을 수 있는 상태들의 집합을 DFA의 한 상태로 삼는 방법입니다. NFA는 한 글자를 읽고 여러 곳으로 동시에 갈 수 있는데, 「갈 수 있는 곳 전부」를 하나의 이름으로 부르면 갈 곳이 하나로 정해져 DFA가 됩니다. NFA와 DFA의 표현력이 같다는 정리의 증명이 곧 이 알고리즘입니다.

어떤 상태 집합에서 글자를 읽지 않고 갈 수 있는 곳을 모두 더한 것입니다. 시작도 시작 상태의 ε-닫힘에서 출발하고, 글자를 읽은 뒤에도 다시 ε-닫힘을 취해야 합니다. 이 두 번째를 빠뜨리는 것이 이 알고리즘에서 가장 흔한 구현 실수입니다.

늘어납니다. 「뒤에서 n번째 글자가 a인 문자열」이 그런 언어입니다. NFA로는 n+1개 상태면 되지만 — a를 하나 찍고 아무 글자나 n−1개 세면 끝입니다 — DFA는 마지막 n글자를 전부 기억해야 하므로 2ⁿ개가 필요합니다. 이 계산기에 그 예제를 넣어 두었고, 최소화해도 하나도 줄지 않는 것까지 확인할 수 있습니다. 기억할 것이 정말 그만큼 있다는 뜻입니다.

DFA는 모든 상태에서 모든 글자에 대해 갈 곳이 있어야 하기 때문입니다. 부분집합 구성에서 어디로도 갈 수 없으면 공집합이 나오는데, 이것을 버리지 않고 죽은 상태로 남겨야 정의를 만족하는 DFA가 됩니다. 함정 상태에서는 어느 글자를 읽어도 자기 자신으로 돌아옵니다.

「받아들이는 상태 / 아닌 상태」 두 덩어리에서 시작해, 같은 덩어리 안인데 어떤 글자로 서로 다른 덩어리로 가는 상태들을 쪼갭니다. 더 쪼갤 수 없을 때 멈추면 그것이 최소 DFA입니다. 마이힐–네로드 정리에 따라 이 최소 DFA는 유일합니다(상태 이름을 빼면).

길이 8 이하 모든 문자열을 원래 NFA·변환된 DFA·최소화된 DFA에 각각 넣어 판정이 모두 같은지 대조합니다. 결과 화면에 몇 개를 대조했는지, 어긋난 것이 있는지 그대로 나옵니다. 어긋나는 문자열이 하나라도 있으면 변환이 잘못된 것입니다.

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