Theory of computation (3)

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

NFA(Nondeterministic Finite Acceptors)
1. 정의 $$M(Q, \Sigma, \delta, q_0, F)$$

• $Q$ : State들의 집합
• $\Sigma$ : input alphabet
• $\delta$ : $Q \times \{\Sigma \cup \{\lambda\}\} \to P(Q)$ transition function
• $q_0$ : $q_0 \in Q$ initial state (1개)
• $F$ : $F \in Q$ Final states (1개 이상 가능)

DFA, NFA의 가장 큰 차이점은 transition function $\delta$ 입니다.

DFA는 state가 결정되고, input alphabet이 결정되면, edge를 통해 갈수 있는 state가 하나 있다. 하지만 NFA는 하나의 state에서 input alphabet이 결정되면 edge를 통해 갈 수 있는 state가 여러개일수 있습니다. 또 DFA는 input alphabet은 하나의 state에 하나만 있지만 NFA는 하나의 state에서 중복된 input alphabet이 있을수 있습니다.

2. 예제

예제 그래프를 통해 이해해보면 좀 더 쉽게 이해할수 있습니다.

위 그림의 start state, final state가 $q_0$입니다.
NFA에서는 DFA와 다르점을 보려면 state $q_1$을 보면 됩니다.
DFA에서는 하나의 state에서는 반드시 input alphabet 1개씩 되어야 하는데 NFA에서는 $q_1$에서와 같이 총 3개의 edge가 있고, symbol $a$가 두번 쓰이는 것을 알수 있습니다. 또한 $\epsilon$ symbol은 transition function으로 쓰이지 않았습니다.

또 다른 예제를 보겠습니다.

위 그림에서는 start state가 $q_0$, final state가 $q_1$ 입니다.
또 다른 기호인 $\lambda$가 보이는데 이것은 특별한 input alphabet이 없어도 다른 state로 transition 될수 있다는 뜻입니다.

예를 들어 $q_2$에서 $\lambda$ string이 들어오면 어느 state에 있을지 알아보면 가능한 state는 $q_0, q_2$가 될것입니다.
즉 $q_0$로 transition되거나, 또는 아무 symbol이 없다는 뜻도 되므로 움직이지 않고 자기 자신 $q_2$에 있을수 있습니다.
식으로 나타내면 다음과 같습니다.

$$\delta(q_2, \lambda)=\{q_0, q_2\}$$

그러면 $\lambda$ 는 NFA가 accept 할지 안할지는 어떻게 판단을 할까요?
판단 방법은 transition을 통해서 나온 state 중에서 final state가 있으면 accept하고 아니면 accept 하지 않습니다. 위 예제에서는 final state가 $q_1$ 이지만, $q_1$ 이 $\lambda$ transition에 의해 나온 state 집합에 없으므로 $\lambda$ 는 accept 하지 않습니다.

그러면 조금 더 심화해서 symbol 하나만으로 transition 하는게 아닌 string으로 transition을 해보겠습니다.

$$\delta ^* (q_1, a)$$

위 방법으로 transition하면 나올수 있는 state는 어떤게 있을까요?

답은 모든 state가 가능합니다 즉 다음과 같습니다.

$$\delta ^* (q_1, a)=\{q_0, q_1, q_2\}$$

$q_1$에서 $q_0$로 transition 할때에는 $\delta ^* (q_1, \lambda \lambda a \lambda \lambda)$ 가 되면 가능합니다.

$q_1$에서 $q_1$로 transition 할때에는 $\delta ^* (q_1, \lambda \lambda a)$ 가 되면 가능합니다.

$q_1$에서 $q_2$로 transition 할때에는 $\delta ^* (q_1, \lambda \lambda a \lambda)$ 가 되면 가능합니다.

위와 같이 모든 state로 이동이 가능할 뿐더러 그러면 당연히 final state도 포함이 되기 때문에 $a$는 accept 이 된다는 것도 알수 있습니다.