DFA 최소화

Myphill-Nerode 정리를 사용한 DFA 최소화

연산

Input − DFA

Output − 최소화 된 DFA

Step 1− 반드시 직접 연결되지 않은 모든 상태 쌍 (Q _i , Q _j )에 대한 표를 그립니다. [초기에는 모두 표시 해제 됨]

Step 2− Q _i ∈ F 및 Q _j ∉ F 또는 그 반대 인 DFA의 모든 상태 쌍 (Q _i , Q _j )을 고려 하고 표시합니다. [여기 F는 최종 상태 집합입니다.]

Step 3 − 더 이상 상태를 표시 할 수 없을 때까지이 단계를 반복합니다. −

표시되지 않은 쌍 (Q _i , Q _j )이있는 경우 일부 입력 알파벳에 대해 쌍 {δ (Q _i , A), δ (Q _i , A)}가 표시되어 있으면 표시하십시오.

Step 4− 표시되지 않은 모든 쌍 (Q _i , Q _j )을 결합하여 축소 된 DFA에서 단일 상태로 만듭니다.

예

알고리즘 2를 사용하여 아래 표시된 DFA를 최소화하겠습니다.

Step 1 − 모든 상태 쌍에 대한 표를 그립니다.

	ㅏ	비	씨	디	이자형	에프
ㅏ
비
씨
디
이자형
에프

Step 2 − 상태 쌍을 표시합니다.

	ㅏ	비	씨	디	이자형	에프
ㅏ
비
씨	✔	✔
디	✔	✔
이자형	✔	✔
에프			✔	✔	✔

Step 3− 녹색 체크 표시로 상태 쌍을 전 이적으로 표시하려고합니다. 상태 'a'와 'f'에 1을 입력하면 각각 'c'와 'f'상태로 이동합니다. (c, f)는 이미 표시되어 있으므로 쌍 (a, f)를 표시합니다. 이제 'b'와 'f'상태에 1을 입력합니다. 각각 'd'와 'f'상태가됩니다. (d, f)는 이미 표시되어 있으므로 쌍 (b, f)를 표시합니다.

	ㅏ	비	씨	디	이자형	에프
ㅏ
비
씨	✔	✔
디	✔	✔
이자형	✔	✔
에프	✔	✔	✔	✔	✔

3 단계 후에는 표시되지 않은 상태 조합 {a, b} {c, d} {c, e} {d, e}가 있습니다.

{c, d} {c, e} {d, e}를 {c, d, e}로 재결합 할 수 있습니다.

따라서 우리는-{a, b} 및 {c, d, e}와 같은 두 가지 결합 상태를 얻었습니다.

따라서 최소화 된 최종 DFA에는 {f}, {a, b} 및 {c, d, e}의 세 가지 상태가 포함됩니다.

등가 정리를 사용한 DFA 최소화

X와 Y가 DFA에서 두 상태 인 경우 구별 할 수없는 경우이 두 상태를 {X, Y}로 결합 할 수 있습니다. δ (X, S) 및 δ (Y, S) 중 하나는 수락하고 다른 하나는 수락하지 않는 문자열 S가 하나 이상있는 경우 두 상태를 구별 할 수 있습니다. 따라서 DFA는 모든 상태를 구별 할 수있는 경우에만 최소입니다.

알고리즘 3

Step 1 − 모든 주 Q 두 개의 파티션으로 나뉩니다. final states 과 non-final states 다음으로 표시됩니다. P₀. 파티션의 모든 상태는 0 ^번째에 해당합니다. 카운터 가져가k 0으로 초기화합니다.

Step 2− k를 1 씩 증가시킵니다. P _k의 각 분할에 대해 k로 구분할 수있는 경우 P _k 의 상태 를 두 분할로 나눕니다 . 이 파티션 X와 Y 내의 두 상태는 입력이있는 경우 k로 구분할 수 있습니다.S 그런 δ(X, S) 과 δ(Y, S) (k-1) 구별 가능합니다.

Step 3− P _k ≠ P _k-1 이면 2 단계를 반복하고 그렇지 않으면 4 단계로 이동합니다.

Step 4− k ^번째 등가 세트를 결합 하여 축소 된 DFA의 새로운 상태로 만듭니다.