오토마타와 형식언어 02 NFA(비결정적 유한 오토마타)

NFA(Nondeterministic Finite Accepter)

1. NFA

   DFA와의 차이점은 같은 input에 대해 transition function이 여러 개인 경우 그 중에 임의로 한 가지를 따라 다음 state로 이동한다.

   \[M = (Q,\Sigma, \delta, q_0, F)\]

   순서대로 internal states, input alphabet, transition function, initial state, final states를 의미한다.

   \[\delta = Q \times (\Sigma \cup\{\lambda\})->2^Q\]

2. Lambda Transition Function

   \(\delta(q_0,\lambda)=q_1\) 즉 문자열을 input 받지 않아도 임의로 다음 state로 전이되는 함수를 말하고, NFA에서만 존재하는 개념이다. 이 때 vertice vi에서 vj로 가기 위해 거치는 lambda edge이 A개 있고, input이 w라면 이 때 length는 최대 A + (A+1)w이다.

3. Extended Transition Function \(\delta^*(q_i,w)=Q_j\) 이 때 DFA와는 다르게, qi에서 출발하여 도달할 수 있는 모든 state들의 집합을 Qj라고 한다.

4. accepted Language DFA에 의해 Accept되는 모든 String의 집합이다.

   \[L(M)=\{w\in\Sigma^*:\delta^*(q_0,w)\cap F\not ={\varnothing} \}\]

   전이 함수를 따라 계속 다음 state로 진행하였을 때 최종적으로 final states에 도달하게 하는 path가 한 가지라도 존재하는 모든 string을 원소로 갖는 집합이 Language이다.

5. NFA vs DFA NFA와 DFA는 본질적으로는 같다. 그러나 복잡한 automata를 표현할 때 NFA가 더 쉽고, NFA graph가 더 이해하기 쉽다.