Nondeterministic Finite Automata 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]

상위 문서: [[Finite Automata#Nondeterministic Finite Automata|Finite Automata]]

==개요==
해당 문서는 finite automata의 한 종류인 NFA(Nondeterministic Finite Automata)에 대해 설명하고, 이를 이용한 정규 언어의 정의 방식을 설명한다.

==NFA Vs. DFA==
DFA(Deterministic Finite Automata)에서는 각 상태와 입력 심볼 쌍 (q, a)에 대해 오직 하나의 전이만 정의된다. 하지만 NFA에서는 하나의 (q,a)에 대해 여러 개의 전이가 있을 수도 있고, 전이가 전혀 없을 수도 있으며, 입력을 소모하지 않고 이동하는 ε-transition도 허용된다. 이때 수용(accept) 조건은 어떤 행운의 선택(lucky choice)"의 전이 경로라도 최종 상태에 도달하면 문자열을 accept하는 것이다. 

이는 figure 1을 통해 설명할 수 있다. 주어진 NFA는 {0,1} 위의 문자열을 입력받아, 끝에서 세 번째 문자가 1인 문자열을 accept한다. 이러한 NFA는 아래와 같은 방식으로 작동한다:
# 계속해서 Q1에서 입력을 소비하다가,
# 어느 순간 "여기가 끝에서 세 번째 자리일 것"이라고 추측(guess)하고 Q2로 이동.
# 그 뒤 정확히 두 개 문자를 더 읽고 Q4에 도착하면 accept.
# 만약 모든 "선택과 추측"이 실패하면, 해당 문자열을 수용되지 않음

==Formal Definition of NFA==
NFA는 DFA 처럼 아래와 같은 5-튜플로 정의된다:
* <math>Q</math>: 유한 상태 집합
* <math>\Sigma</math>: 유한 입력 기호 집합(입력 알파벳)
* <math>\delta</math>: <math>Q\times (\Sigma \cup \{\epsilon\} \rightarrow \mathcal{P}(Q))</math>: 전이 함수(transition function)
** 이는 DFA의 그것과는 다르게 “다음 상태 하나”가 아니라 “가능한 다음 상태들의 집합”을 반환한다.
** ε-transition이 발행하여 입력 문자를 읽지 않고도 상태가 바뀔 수 있다.
* <math>q_0 \in Q</math>: 시작 상태(start state)
* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)

==각주==