1. DFA: DFA는 결정론적 유한 오토마톤(Deterministic Finite Automaton)을 의미합니다. 유한 오토마타(FA)는 입력 기호에 해당하는 경우 결정론적이라고 하며 단일 결과 상태, 즉 전환이 하나만 있는 경우입니다. 결정론적 유한 오토마타는 다음과 같이 표현되는 5개의 튜플 세트입니다.

어디,
Q: 유한 제어(qo, q1, q2, …)의 비어 있지 않은 유한 상태 집합입니다.
Σ: 입력 기호의 비어 있지 않은 유한 집합입니다.
δ: 두 개의 인수인 상태와 입력 기호를 사용하는 전이 함수로 단일 상태를 반환합니다.
qo: Q의 상태 중 하나인 시작 상태입니다.
F: Q에 속한 세트의 상태를 수락하는 비어 있지 않은 최종 상태 세트입니다.

2. 원인:
NFA는 비결정적 유한 오토마톤(Nondeterministic Finite Automaton)을 나타냅니다. 유한 오토마타(FA)는 동일한 입력 기호에 대해 한 상태에서 둘 이상의 가능한 전환이 있는 경우 비결정적이라고 합니다.
비결정론적 유한 오토마타도 5개의 튜플 세트이며 다음과 같이 표현됩니다.

어디,
Q: 비어 있지 않은 유한 상태의 집합입니다.
Σ: 비어 있지 않은 유한 입력 기호 세트.
δ: Q에서 상태를 취하고 Q의 하위 집합을 입력 기호로 반환하는 전이 함수입니다.
qo: NFA의 초기 상태이자 Q의 멤버입니다.
F: 비어 있지 않은 최종 상태 세트와 Q의 멤버입니다.

전제 조건 – 자동 완료

DFA와 NFA의 차이점: