[암호학] 9. Non-Deterministic Finite Automata (NFA)

NFA (Non-Deterministic Finite Automata)

이번엔 "비결정적 유한 오토마타"이다.

역시 상태는 유한하지만 입력이 들어오면 이동할 상태가 비결정적이라는 뜻이다.

NFA는 다음으로 이루어져있다.

$M = (Q, \Sigma, q, F, s)$

• $Q$ : NFA상태들의 집합
• $\Sigma$ : 입력받은 String
• $q$ : 초기상태 ($q \in Q$)
• $F$ : AC를 받는 상태들의 집합($F \in Q$, 여러개 가능)
• $s$ : Transition Relation

DFA와 대부분 같은데 $s$의 의미만 다르다.

DFA는 이동할 상태가 결정적이기 때문에 경로가 유일하지만 NFA는 모든 경로로 이동을 할 수 있기 때문에 Relation이라는 용어를 쓰는 것 같다.

 

Problem X3 를 DFA로 그리면 다음과 같았었다.

X3 DFA

이것을 NFA로 나타내면 다음과 같다.

X3 NFA

뭔가 굉장히 단순해졌다.

여기에 X3을 AC하는 1010을 넣어보자.

1. $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 4$

2. $1 \rightarrow 1 \rightarrow 1 \rightarrow 1 \rightarrow 1$

3. $1 \rightarrow 1 \rightarrow 1 \rightarrow 2 \rightarrow 3$

같이 여러 경로가 가능할 것이다.

그 중에서 AC를 받을 수 있는 경로는 1번 경로만 가능하다.

 

위에서 봤듯이 NFA는 여러개의 경로를 시뮬레이션 하면서 한 가지 경로라도 AC를 받으면 NFA가 문제를 해결했다고 볼 수 있다.

 

당연히 DFA보다 많은 시간이 필요할 것 같은데 왜 사용할까?

우선 DFA보다 간략하기 때문에 생각하기 쉽다.

그리고 NFA로 나타낼 수 있다면 DFA로 나타낼 수 있다.

 

그래서 어떤 문제를 보면 NFA로 나타내보고 DFA로 바꾸는게 쉽다.