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

FA의 공식적인 정의

유한 오토마타는 5-튜플(Q, ∑, δ, q0, F)의 모음입니다. 여기서:

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

유한 오토마타 모델:

유한 오토마타는 입력 테이프와 유한 제어로 표현될 수 있습니다.

입력 테이프: 일정 수의 셀을 갖는 선형 테이프입니다. 각 입력 기호는 각 셀에 배치됩니다.

유한 제어: 유한 제어는 입력 테이프로부터 특정 입력을 받으면 다음 상태를 결정합니다. 테이프 리더는 셀을 왼쪽에서 오른쪽으로 하나씩 읽으며, 한 번에 하나의 입력 기호만 읽습니다.

오토마타의 종류:

유한 오토마타에는 두 가지 유형이 있습니다.

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

1. DFA

DFA는 결정론적 유한 오토마타를 의미합니다. 결정론적이란 계산의 고유성을 나타냅니다. DFA에서 기계는 특정 입력 문자에 대해서만 하나의 상태로 전환됩니다. DFA는 null 이동을 허용하지 않습니다.

2. NFA

NFA는 비결정적 유한 오토마타를 의미합니다. 특정 입력에 대해 여러 가지 상태를 전송하는 데 사용됩니다. null 이동을 허용할 수 있습니다.

DFA 및 NFA에 대한 몇 가지 중요한 사항:

1. 모든 DFA는 NFA이지만 NFA는 DFA가 아닙니다.
2. NFA와 DFA 모두에 여러 최종 상태가 있을 수 있습니다.
3. DFA는 컴파일러의 어휘 분석에 사용됩니다.
4. NFA는 이론적인 개념에 가깝습니다.