오토마타의 정의

오토마타(Automata)의 수학적 정의는 다음과 같습니다.

오토마타는 입력을 처리하여 특정 언어나 계산을 수행하는 추상적 기계로서, 주로 다음의 구성요소로 정의됩니다.

오토마타 A는 5개의 원소로 구성된 집합으로 표현됩니다.

A = (Q, Σ, δ, q₀, F)

여기서,

Q : 상태(state)의 유한집합

Σ : 입력 알파벳(input alphabet)의 유한집합

δ : 전이함수(transition function)
(δ: Q × Σ → Q 또는 Q의 멱집합)

q₀ : 시작상태(start state), q₀ ∈ Q

F : 종료상태(final states) 또는 수락상태(accepting states)의 집합, F ⊆ Q


이 정의는 유한 오토마타(Finite Automata)의 정의이며, 오토마타 종류(유한 오토마타, 푸시다운 오토마타, 튜링 머신)에 따라 전이함수 δ 및 추가적인 자료구조(예: 스택, 테이프)가 달라질 수 있습니다.

간단히 말하면, 오토마타는 특정 상태에서 입력 기호를 받아 상태를 전환하며 입력 전체를 읽었을 때 최종적으로 종료상태에 도달하는지 여부로 입력 문자열의 수락 여부를 결정하는 수학적 구조입니다.