오토마타 이론
오토마타 이론(영어: Automata Theory)은 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야이다. 여기서 추상 기계를 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형), 즉 자동 기계라고 부른다. 이 이름은 '자동'을 의미하는 그리스어 'αὐτόματα'에서 유래하였다.
일반적으로 오토마타는 적어도 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며, 출력을 내놓는다. 이는 알고리즘이 요구하는 것, 즉 계산 문제를 해결할 능력과 같다. 계산 문제는 일반적으로 오토마타의 능력에 맞게 결정 문제로 환산되며, 이 때 추상 기계와 형식 언어, 형식 문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 같은 계층 분류를 갖는다.
오토마톤 이론이란 오토마톤을 연구하는 학문이지만, 다른 표현 방식을 빌린다면 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’에 관계되는 것이다. 그리고 대상의 구성요소의 성질 등에는 그리 관여하지 않는다.[출처 필요] 오토마타는 계산이론, 인공지능, 컴퓨터 구조 설계와 컴파일러 설계, 파싱, 정형 검증 등의 중요한 요소다.
오토마타
편집오토마타는 이산 시간 동안 주어진 입력에 의존해 작동하는 수학적인 기계이다. 기계는 일정 주기마다 입력을 하나씩 받는데, 이를 기호 또는 문자라고 한다. 기계가 입력받는 문자는 정해진 집합의 한 원소여야 하며, 이를 알파벳이라 한다. 기계가 입력받는 일련의 기호와 문자를 문자열이라 한다. 기계는 유한한 상태의 집합을 갖고 있으며, 입력에 따라 현재 상태에서 정해진 다음 상태로 전이한다. 현재 상태와 입력, 다음 상태는 수학적으로 함수 또는 관계로 주어진다. 이를 전이 함수 또는 전이 관계라 한다. 기계는 입력의 끝을 만나거나 특정 상태에 있을 때 정지할 수 있다. 기계는 정지했을 때 문자열을 수용하거나 거부한다.
형식 정의
편집- Q: 상태의 공집합이 아닌 유한집합.
- Σ: 알파벳입력(입출력) 문자의 공집합이 아닌 합
- :첫 상태인 Q의 원소.
- F: 끝 상태의 공집합이 아닌 Q의 부분집합. 끝 상태에서 상태가 직접 수용이나 거부를 정하는 경우 Faccept, Freject로 구분한다.
- Γ: 기억 장소의 알파벳. (선택적)
- δ: 전이 함수. 일반적으로 δ: Q × Σ → Q . 다음과 같은 δ의 정의들이 가능하며, 이에 따라 오토마타의 종류를 구분한다.
- 정의역이 Q × (Σ ∪ {ε})인 경우.
- 치역이 2Q인 경우.
- 정의역이 Q × Σ × Γ인 경우. 또는 알파벳의 집합이 {ε}와의 합집합.
- 치역이 Q × Σ, Q × Γ, Q × Σ × Γ인 경우. 또는 알파벳의 집합이 {ε}와의 합집합.
- 정의역의 Q가 Q - {F} 또는 Q - {Faccept, Freject}인 경우.
- 치역이 Q × Σ × {R}, Q × Σ × {L, R}, Q × Σ × {L, R, N}인 경우 등.
- 여기서 ε은 빈 문자열(길이가 0)이다.
작동
편집오토마타의 작동은 입력 문자열, 출력 문자열 (선택적), 기억 장소 (선택적)에 따라 형상 (계산)(en:configuration)에서 형상으로의 전이로 표현된다.
- w: 문자열. 문자열은 가능한 모든 문자열의 한 원소이다.
- w ∈ Σ*이고, |w| = n일 때 w = s0s1s2...sn-1
- 여기서 Σ*는 알파벳의 클레이니 스타이다.
- L: 언어. 집합 L⊆Σ*에 대해, 기계 M이 수용하는 모든 문자열 w에 대해서만 w∈L일 때 L은 M이 인지하는 언어이다.
- q0w = q0s0...sn-1: 처음 형상(q0 = S). 일반적으로 입력 문자열은 초기 상태에 있는 기계가 다음 단계에 읽을 수 있도록 대기되어 있는 것으로 한다.
- w'qf = q0s0'...sm-1'qf: 마지막 형상(qf ∈ F)의 한 예.
