• NFA는 비결정적 유한 오토마타를 의미합니다. 특정 정규 언어에 대해서는 DFA보다 NFA를 구성하는 것이 쉽습니다.
• 유한 오토마타는 현재 상태에서 다음 상태까지 특정 입력에 대한 경로가 많을 때 NFA라고 합니다.
• 모든 NFA는 DFA가 아니지만 각 NFA는 DFA로 변환될 수 있습니다.
• NFA는 DFA와 동일한 방식으로 정의되지만 다음 두 가지 예외를 제외하면 여러 개의 다음 상태를 포함하고 ε 전이를 포함합니다.

다음 이미지에서 우리는 입력 a에 대한 상태 q0에서 두 개의 다음 상태 q1과 q2가 있음을 볼 수 있습니다. 마찬가지로 입력 b에 대한 q0에서 다음 상태는 q0과 q1입니다. 따라서 특정 입력을 사용하여 다음에 어디로 갈지 고정되거나 결정되지 않습니다. 따라서 이 FA를 비결정론적 유한 오토마타라고 합니다.

NFA의 공식 정의:

NFA에는 다음과 같이 DFA와 동일하지만 전환 기능이 다른 5가지 상태가 있습니다.

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

어디,

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

NFA의 그래픽 표현

NFA는 상태 다이어그램이라는 이중 그래프로 표시될 수 있습니다. 그 내용은 다음과 같습니다.

이 xd는 무슨 뜻인가요?

1. 상태는 정점으로 표현됩니다.
2. 입력 문자로 표시된 호는 전환을 나타냅니다.
3. 초기 상태는 화살표로 표시됩니다.
4. 최종 상태는 이중 원으로 표시됩니다.

예시 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

해결책:

전환 다이어그램:

각도 cli 제거

전환 테이블:

위 다이어그램에서 현재 상태가 q0일 때 입력 0에서 다음 상태는 q0 또는 q1이 되고 입력 1에서 다음 상태는 q1이 되는 것을 볼 수 있습니다. 현재 상태가 q1이면 입력 0에서 다음 상태는 q2가 되고 입력 1에서 다음 상태는 q0이 됩니다. 현재 상태가 q2이면 입력이 0이면 다음 상태는 q2이고, 입력이 1이면 다음 상태는 q1 또는 q2가 됩니다.

예 2:

∑ = {0, 1}인 NFA는 01인 모든 문자열을 허용합니다.

해결책:

순서대로

전환 테이블:

예시 3:

∑ = {0, 1}인 NFA이며 길이가 2 이상인 모든 문자열을 허용합니다.

해결책:

전환 테이블: