Constructing Minimal DFA using Myhill-Nerode Theorem

 

 

 

 

---

Myhill-Nerode Theorem

---

 

 

 

하나의 Language에 있어서 그에 적합한 DFA는 많지만, 최소화된 상태의 DFA는 하나뿐입니다.

따라서 DFA를 최소화시키기 위한 다양한 이론들이 있는데, 오늘은 Myhill-Nerode Theorem에 대해서 공부하고, 적용시켜보려고 합니다.

 

 

1. 기본적인 DFA minimizing method

 

DFA가 필요 이상으로 늘어나는 이유는 줄일 수 있는 states를 과도하게 늘려서입니다.

따라서 같은 입력과 같은 출력을 내뱉는 states들에 대해 "indistinguishable"하다라고 표현합니다.

기호로는 다음과 같이 표현할 수 있습니다.

 

Two states, s and t, are equivalent if for all possible stings w, T(s, w) and T(t, w) are both either accepting or non-accepting.

 

그럼 DFA를 최소화하기 위해서는 당연히 indistinguishable한 state들을 하나로 합쳐버리면 되겠죠?

그렇게 사용할 수 있는 방법들 중 하나가 오늘 다룰 Myhill-Nerode Theorem입니다.

본격적으로 Theorem을 보기 전에, indistinguishable states에 대한 정의를 내리고 갑시다.

 

p & q : indistinguishable if 𝛿*(q, w)∈F iff 𝛿*(q, w)∈F for all w∈ Σ* p & q : distinguishable if 𝛿*(q, w)∈F and 𝛿*(q, w)∈F for some w∈ Σ*

 

기호만 화려하지 그냥 input과 output이 같다는 소리죠?

 

 

2. Myhill-Nerode Theorem

 

우선 Myhill-Nerode Theorem은 Table Filling Method로도 많이 알려져있습니다. 

풀어서 설명한 과정은 다음과 같습니다.

 

1) Draw a table for all pairs of states (P, Q)

2) Mark all pairs where P∈F and Q∉F

3) If there are any Unmarked pairs (P,Q) such that [𝛿(P,x), 𝛿(Q,x)] is marked, the mark [P, Q] (where x is an input symbol)

Repeat this until no more markings can be made.

4) Combine all the Unmarked Pairs and make them a single state in the minimized DFA

 

말로만 서술하면 이해하기 힘들기 때문에 예시와 함께 설명하겠습니다.

 

 

다음 dfa에 대해서 최소화를 시킵시다.

 

1) Draw a table for all pairs of states (P, Q)

 

모든 칸을 그리지 않는 이유는 두 쌍에 대한 관계만 따지면 되기 때문입니다. (ex. {0, 1}과 {1,0}은 같음)

2) Mark all pairs where P∈F and Q∉F

 

본 DFA에서 4만 accepting state이고 나머지는 모두 accepting state가 아니기 때문에 (4,0), (4,1), (4,2), (4,3)은 모두 제외대상이다.

 

3) If there are any Unmarked pairs (P,Q) such that [𝛿(P,x), 𝛿(Q,x)] is marked, the mark [P, Q] (where x is an input symbol)

Repeat this until no more markings can be made.

 

계속해서 반복한 결과 {1, 2, 3}이 모두 indistiguishable하다는 것을 알 수 있습니다.

따라서 결과도 함께 합해준다면?

4) Combine all the Unmarked Pairs and make them a single state in the minimized DFA

 

 

이런식으로 해주면 되겠습니당

 

3. Proving a DFA is minimal

 

그렇다면 마지막으로 DFA가 최소화된 상태라고 증명은 어떻게 할 수 있을까요?

indistinguishable한 state가 있는 경우 이를 합치는 것이 최소화의 과정이였으니, 단순하게 모든 state가 distinguishable하다고 증명을 하면 되겠죠?

 

방법은 그냥 위에서 진행했던 table그려서 하는 과정을 똑같이 반복하면 되겠습니다. 만약 위 예시의 정답을 가지고 진행하면 모든 state끼리의 관계가 distinguishable하다는 것을 도출 할 수 있고, 따라서 dfa는 더이상 줄일 수 없다는 결론을 낼 수 있겠죠?