오토마타와 형식언어 03
오토마타와 형식언어 03 NFA(비결정적 유한 오토마타)
NFA(Nondeterministic Finite Accepter)
NFA
DFA와의 차이점은 같은
\[M = (Q,\Sigma, \delta, q_0, F)\]input
에 대해transition function
이 여러 개인 경우 그 중에 임의로 한 가지를 따라 다음state
로 이동한다.순서대로
\[\delta = Q \times (\Sigma \cup\{\lambda\})->2^Q\]internal states
,input alphabet
,transition function
,initial state
,final states
를 의미한다.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
이다.Extended Transition Function
\(\delta^*(q_i,w)=Q_j\) 이 때 DFA와는 다르게,qi
에서 출발하여 도달할 수 있는 모든state
들의 집합을 Qj라고 한다.
\[L(M)=\{w\in\Sigma^*:\delta^*(q_0,w)\cap F\not ={\varnothing} \}\]accepted Language
DFA에 의해 Accept되는 모든 String의 집합이다.전이 함수를 따라 계속 다음
state
로 진행하였을 때 최종적으로final states
에 도달하게 하는 path가 한 가지라도 존재하는 모든string
을 원소로 갖는 집합이Language
이다.NFA vs DFA
NFA와 DFA는 본질적으로는 같다. 그러나 복잡한 automata를 표현할 때 NFA가 더 쉽고, NFA graph가 더 이해하기 쉽다.