결정 론적 유한 오토 마톤

유한 오토 마톤은 두 가지 유형으로 분류 할 수 있습니다.

• 결정 론적 유한 오토 마톤 (DFA)
• 비 결정적 유한 오토 마톤 (NDFA / NFA)

결정 론적 유한 오토 마톤 (DFA)

DFA에서는 각 입력 기호에 대해 머신이 이동할 상태를 결정할 수 있습니다. 따라서Deterministic Automaton. 유한 수의 상태를 가지고 있기 때문에 기계는Deterministic Finite Machine 또는 Deterministic Finite Automaton.

DFA의 공식적인 정의

DFA는 5- 튜플 (Q, ∑, δ, q ₀ , F) 로 표현할 수 있습니다.

• Q 유한 한 상태 집합입니다.

• ∑ 알파벳이라고하는 유한 한 기호 집합입니다.

• δ δ : Q × ∑ → Q

• q₀입력이 처리되는 초기 상태입니다 (q ₀ ∈ Q).

• F Q (F ⊆ Q)의 최종 상태 / 상태 집합입니다.

DFA의 그래픽 표현

DFA는 state diagram.

• 정점은 상태를 나타냅니다.
• 입력 알파벳으로 표시된 호는 전환을 보여줍니다.
• 초기 상태는 빈 단일 들어오는 호로 표시됩니다.
• 최종 상태는 이중 원으로 표시됩니다.

예

결정 론적 유한 오토 마톤을 →

• Q = {a, b, c},
• ∑ = {0, 1},
• q ₀ = {a},
• F = {c} 및

다음 표에 표시된 전이 함수 δ-

현재 상태	입력 0의 다음 상태	입력 1의 다음 상태
a	ㅏ	비
b	씨	ㅏ
c	비	씨

그래픽 표현은 다음과 같습니다.