오토마타와 형식언어 04 Equivalence of DFA and NFA and Reduction

Equivalence

1. equivalent

   다음 식을 만족하는 경우 equivalent라고 한다. \(L(M_1) = L(M_2)\) 이 때 주어진 Language를 만족하는 accepters는 매우 다양하고, 유일하지 않다.

2. NFA to DFA

   NFA에서 각 state에 모든 symbol을 input으로 한 전이 함수의 결과인 set을 DFA에서의 new state로 정의한다. 그 후 새로 만들어진 set state에 대해서도 symbol을 넣은 결과를 또다른 set state로 표현할 수 있다.

Reduction

1. indistinguishable

   모든 w에 대해, 다음의 두 가지 조건을 모두 만족하면 p와 q는 indistinguishable이다.

   1. p에서 w를 넣어 최종적으로 final state에 도달하는 길이 존재한다면, q에서도 마찬가지로 final state에 도착하는 길이 존재해야한다.
   2. p에서 final state에 도착하는 길이 존재하지 않으면 q에서도 존재하지 않아야한다.

2. distinguishable

   위의 조건에 만족하지 않는 w가 존재한다면, p와 q는 distinguishable하다.

3. Transitivity

   p와 q가 indistinguishable하고, q와 r이 indistinguishable하다면, p와 r도 indistinguishable하다.

indistinguishable과 distinguishable를 나누는 이유는 indistinguishable하다면 state를 merge하여 reduction하기 위함이다. 그러기 위해서는 모든 state 들이 indistinguishable한지 판단하여야 한다. 그러기 위해서 다음의 방법이 있다.

1. 접근할 수 없는 모든 state를 지운다.
2. 모든 (p, q)를 고려하고, 고려한 것은 mark한다.
3. 2번을 반복하고, 더이상 unmark가 없으면 그만둔다.

이 과정에서 모든 (p,q)를 w를 넣어 최종적으로 final state에 도달하는 길이 존재하는지 판단하는 것은 어렵기 때문에 다음의 결론이 있다.

p에서 a를 넣은 state를 pa, q에서 a를 넣은 state를 qa라고 할 때, pq와 qa가 distinguishable하다면 p와 q도 distinguishable하다.

final state에서부터 이전으로 한 칸씩 이동하면서 위의 정리를 이용하면 모든 state에 대해 구할 수 있다.

결론적으로, 위의 방법을 이용하면 모든 state 중 indistinguishable한 state들을 집합으로 묶어서 partition으로 표현할 수 있다. \(\{q_0\}, \{q_1,q_3\},\{q_2\}, \{q_4\}\)