비결정적 유한 인식기(nfa)

비결정적 유한 인식기(nfa)는 다음과 같이 정의 된다.

$$ M=(Q,\Sigma,\delta,q_0,F)$$

Q,∑,q_0,F는 dfa에서와 같이 정의되고, δ는 다음과 같다.

$$\delta : Q * (\Sigma \cup \{\lambda\})->2^Q$$

내부 상태 Q에서 람다를 포함한 심벌들의 전이함수는 Q의 멱집합이 될 수 있다. 무슨 뜻이냐면 내부상태 q_0에서 다음과 같은 전이 함수가 있다 가정했을때, 다음상태를 여러개가 될 수 있다는 뜻이다.

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

즉 dfa는 방향 그래프에서 현재 상태는 하나의 심벌에 대해 하나의 간선만 진출 간선만 가질수 있지만, nfa에서는 여러개의 진출 간선을 가질수 있다는 것이다. 

또한 nfa는 λ(람다)를 허용하는데, 이는 입력심벌을 읽지 않고도 상태 전이를 할 수 있음을 의미한다. 그리고 δ(q_i,a)는 공집합 일 수 있으며,어떤 상황에 대하여 정의된 전이가 없을을 의미한다.

간단하게 설명하자면, 왼쪽은 dfa이고 오른쪽은 nfa이다.

 

nfa에서의 언어는 확장전이 함수에 의해 정의된다.

$$nfa M=(Q,\Sigma,\delta,q_0,F) $$

에 의해 인식되는 언어는 다음과 같이 정의된다.

$$L(M)=\{w\in\Sigma^*:\delta^*(q_0,w)\cap F\neq 0\}$$

그리고 nfa에서 전이함수가 정의 되어 있지 않아 더이상 움직 일 수 없을때의 상황을 종말 형상이라 한다.