Theory of computation (4)

본 내용은 KOCW 한양대학교 “오토마타 및 계산이론” 강좌 4, 5강을 보며 정리한 내용입니다.

converting NFA to DFA
이번 글에서는 NFA를 DFA로 변형하는 방법을 정리하였습니다.  위 NFA를 DFA로 표현하여 보겠습니다. initial state $q_0$ 에서 transition 해서 갈수 있는 state를 알아보겠습니다. $$\delta (\{q_0\}, a) = \{q_1, q_2\}$$ $$\delta (\{q_0\}, b) = \phi$$ 그래프로 나타내면 아래 그림과 같습니다.  그 다음에 state $\{q_1, q_2\}$ 에서 a, b transition 을 하면 어느 state로 가는지 알아보겠습니다. $$\delta (\{q_1, q_2\}, a) = \{q_1, q_2\}$$ $$\delta (\{q_1, q_2\}, b) = \{q_0\}$$ 그래프로 나타내면 아래 그림과 같습니다.  마지막으로 $\phi$ 에서 transition 해서 갈수 있는 state를 알아보겠습니다. $$\delta (\phi, a) = \phi$$ $$\delta (\phi, b) = \phi$$ 그래프로 나타내면 아래 그림과 같습니다.  위의 과정으로 NFA에서 DFA로 변형하였습니다. distinguishable / undistinguishable

NFA를 DFA로 변환하는 알고리즘을 배우는데 중요한 개념인 state간의 distinguishable / undistinguishable 관계에 대해서 알아보도록 하겠습니다.

undistinguishable

예를 들어 $a$,$b$ state가 있고, $c$라는 final state가 있다고 합시다.
만약 모든 string $w$ 에 대해서 $a$, $b$를 transition 했을때, 두 state 모두 final state $c$에 도달하거나, 아니면 두 state 모두 final state에 도달하지 않으면 state $a$, $b$ 는 undistinguishable 이라고 합니다.

distinguishable (by a string w)

반면에 $a$ 가 final state로 가고 $b$ 가 final state로 가지 않거나, $a$ 가 final state로 가지 않고 $b$ 가 final state로 가는 string $w$ 가 하나라도 존재하면 2개의 state 가 distinguishable 이라고 합니다.

예제 그래프를 통해 이해하는게 더 쉬우니 그래프를 통해 이해해보겠습니다.

먼저 $w$를 $\lambda$ 라고 한다면 어떤 state가 서로 distinguishable 한지 undistinguishable 한지 알아보겠습니다.

$$w=\lambda$$ $$\delta(\{q_0\},w)={q_0}$$ $$\delta(\{q_1\},w)={q_1}$$ $$\delta(\{q_2\},w)={q_2}$$ $$\delta(\{q_3\},w)={q_3}$$ $$\delta(\{q_4\},w)={q_4}$$ $$\delta(\{q_5\},w)={q_5}$$

$\{q_0, q_3, q_5\}$ 는 서로 undistinguishable 하고, $\{q_1, q_2, q_4\}$ 도 서로 undistinguishable 합니다.

$\{q_0, q_3, q_5\}$, $\{q_1, q_2, q_4\}$ 는 서로 undistinguishable 합니다. $w(\lambda)$ string transition 했을때, $\{q_0, q_3, q_5\}$ 는 각각 자기 자신 state로 남으며 자기 자신 state들은 final state가 아니며, $\{q_1, q_2, q_4\}$ 도 역시 자신 state에 남으며 final state로 모두 같습니다.

그래서 다음과 같이 쪼갤수 있습니다.

$$\{q_0, q_3, q_5\}, \{q_1, q_2, q_4\}$$

잘 보면 final state 와 final state가 아닌 state로 쪼개지는 것을 알수있습니다.

$w$를 0,1 이라고 한다면 어떤 state가 서로 distinguishable 한지 undistinguishable 한지 알아보겠습니다.

$\{q_0, q_3, q_5\}, \{q_1, q_2, q_4\}$ 는 서로 distinguishable 하기 때문에 따로 생각을 해보겠습니다.

먼저 $\{q_0, q_3, q_5\}$ 안에서 또 distinguishable 한 state가 있는지 확인을 해보겠습니다.

$$w=0$$ $$\delta(\{q_0\},w)={q_3}$$ $$\delta(\{q_3\},w)={q_0}$$ $$\delta(\{q_5\},w)={q_5}$$

$w = 0$ 일 때는 3개의 state는 transition 했을때 모두 final state가 아닌 곳에 가므로 서로 undistinguishable 합니다.

$$w=1$$ $$\delta(\{q_0\},w)={q_1}$$ $$\delta(\{q_3\},w)={q_4}$$ $$\delta(\{q_5\},w)={q_5}$$

$w = 1$ 일 때는 $\{q_0, q_3\}$과 $\{q_5\}$가 distinguishable 한것을 알수있습니다. $q_0, q_3$는 final state 인곳으로 가지만, $q_5$ 는 final state가 아닌 곳으로 가기 때문입니다.

이제 $\{q_1, q_2, q_4\}$ 안에서 또 distinguishable 한 state가 있는지 확인을 해보겠습니다.

$$w=0$$ $$\delta(\{q_1\},w)={q_2}$$ $$\delta(\{q_2\},w)={q_2}$$ $$\delta(\{q_4\},w)={q_2}$$

세 state 모두 final state로 이동하기 때문에 distinguishable 한 state는 없습니다.

$$w=1$$ $$\delta(\{q_1\},w)={q_5}$$ $$\delta(\{q_2\},w)={q_5}$$ $$\delta(\{q_4\},w)={q_5}$$

세 state 모두 final state가 아닌 곳으로 이동하기 때문에 distinguishable 한 state는 없습니다.

따라서 $w = 0,1$일 때 확인한 distinguishable / undistinguishable state들은 다음과 같습니다.

$$\{q_0, q_3\}, \{q_5\}, \{q_1, q_2, q_4\}$$

$w$를 00,01,10,11 이라고 한다면 어떤 state가 서로 distinguishable 한지 undistinguishable 한지 알아보겠습니다.

이제는 $\{q_0, q_3\}$, $ \{q_1, q_2, q_4\}$ 를 확인하면 됩니다.

먼저 $\{q_0, q_3\}$를 먼저 확인해 보겠습니다.

$$w=00$$ $$\delta(\{q_0\},w)={q_3}$$ $$\delta(\{q_3\},w)={q_0}$$

두 transition state 모두 final state가 아니므로 distinguishable 하지 않습니다.

$$w=01$$ $$\delta(\{q_0\},w)={q_4}$$ $$\delta(\{q_3\},w)={q_1}$$

두 transition state 모두 final state 이므로 distinguishable 하지 않습니다.

$$w=10$$ $$\delta(\{q_0\},w)={q_2}$$ $$\delta(\{q_3\},w)={q_2}$$

두 transition state 모두 final state 이므로 distinguishable 하지 않습니다.

$$w=11$$ $$\delta(\{q_0\},w)={q_5}$$ $$\delta(\{q_3\},w)={q_5}$$

두 transition state 모두 final state가 아니므로 distinguishable 하지 않습니다.

결과적으로 $q_0, q_3$은 서로 undistinguishable 합니다.

이제 $ \{q_1, q_2, q_4\}$를 확인해보겠습니다.

$$w=00$$ $$\delta(\{q_1\},w)={q_2}$$ $$\delta(\{q_2\},w)={q_2}$$ $$\delta(\{q_4\},w)={q_2}$$

transition state 모두 final state 이므로 distinguishable 하지 않습니다.

$$w=10$$ $$\delta(\{q_1\},w)={q_5}$$ $$\delta(\{q_2\},w)={q_5}$$ $$\delta(\{q_4\},w)={q_5}$$

transition state 모두 final state가 아니므로 distinguishable 하지 않습니다.

$$w=01$$ $$\delta(\{q_1\},w)={q_5}$$ $$\delta(\{q_2\},w)={q_5}$$ $$\delta(\{q_4\},w)={q_5}$$

transition state 모두 final state가 아니므로 distinguishable 하지 않습니다.

$$w=11$$ $$\delta(\{q_1\},w)={q_5}$$ $$\delta(\{q_2\},w)={q_5}$$ $$\delta(\{q_4\},w)={q_5}$$

transition state 모두 final state가 아니므로 distinguishable 하지 않습니다.

최종적으로 모두 확인한 state는 모두 undistinguishable 입니다.

이제는 더이상 쪼개지지 않는다는 것을 알수있습니다

최종적인 distinguishable undistinguishable 관계는 다음과 같습니다.

$$\{q_0, q_3\}, \{q_5\}, \{q_1, q_2, q_4\}$$

그러면 다음과 같은 그래프를 그릴수 있습니다

그래프를 보시면 undistinguishable 한것은 같은 state로 묶어줄수 있습니다.