• 유한 상태 기계는 패턴을 인식하는 데 사용됩니다.
• 유한 오토마타 기계는 기호 문자열을 입력으로 받아들이고 그에 따라 상태를 변경합니다. 입력에서 원하는 기호가 발견되면 전환이 발생합니다.
• 전환하는 동안 오토마타는 다음 상태로 이동하거나 동일한 상태를 유지할 수 있습니다.
• FA에는 승인 상태와 거부 상태라는 두 가지 상태가 있습니다. 입력 문자열이 성공적으로 처리되고 오토마타가 최종 상태에 도달하면 수락됩니다.

유한 오토마타는 다음으로 구성됩니다.

Q: 상태의 유한 집합
∑ : 입력 기호의 유한 집합
q0: 초기 상태
F: 최종 상태
d: 전환 기능

전환 함수는 다음과 같이 정의할 수 있습니다.

 δ: Q x ∑ →Q 

FA는 두 가지 방식으로 특징지어집니다.

1. DFA(유한 오토마타)
2. NDFA(비결정론적 유한 오토마타)

DFA

DFA는 Deterministic Finite Automata의 약자입니다. 결정론적이란 계산의 고유성을 나타냅니다. DFA에서 입력 문자는 한 가지 상태로만 이동합니다. DFA는 입력 문자 없이는 DFA가 상태를 변경할 수 없음을 의미하는 null 이동을 허용하지 않습니다.

DFA에는 5개의 튜플 {Q, ∑, q0, F, δ}가 있습니다.

예

결정론적 유한 오토마타의 예를 참조하세요.

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

NDFA

NDFA는 비결정론적 유한 오토마타(Non Deterministic Finite Automata)를 나타냅니다. 특정 입력에 대해 여러 상태를 전송하는 데 사용됩니다. NDFA는 기호를 읽지 않고도 상태를 변경할 수 있음을 의미하는 NULL 이동을 허용합니다.

NDFA에도 DFA와 동일한 5가지 상태가 있습니다. 그러나 NDFA에는 다른 전환 기능이 있습니다.

NDFA의 전환 기능은 다음과 같이 정의할 수 있습니다.

예

비결정론적 유한 오토마타의 예를 참조하세요.

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