컴퓨터야 알아서 처리좀 부탁해 : 오토마타(오토매틱, 자동화) 이론

이미테이션 게임(2014)로 인해 암호를 자동하는 기계를 만든 앨런 튜링에 대한 이야기를 볼 수 있었다. 사실 앨런 튜링이 만든 "에그니마"가 오토마타 이론을 직관적으로 잘 보여준다고 할 수 있다. 입력된 암호 값을 자동으로 해독하는 과정을 거치기 때문이다.

오토마타 이론(영어: Automata Theory)은 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야이다. 여기서 추상 기계를 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형), 즉 자동 기계라고 부른다. 이 이름은 '자동'을 의미하는 그리스어 'αὐτόματα'에서 유래하였다. 

일반적으로 오토마타는 적어도 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며, 출력을 내놓는다. 이는 알고리즘이 요구하는 것, 즉 계산 문제를 해결할 능력과 같다. 계산 문제는 일반적으로 오토마타의 능력에 맞게 결정 문제로 환산되며, 이 때 추상 기계와 형식 언어, 형식 문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 같은 계층 분류를 갖는다.

오토마톤 이론이란 오토마톤을 연구하는 학문이지만, 다른 표현 방식을 빌린다면 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’에 관계되는 것이다. 그리고 대상의 구성요소의 성질 등에는 그리 관여하지 않는다.

오토마타는 컴퓨터 구조 설계와 컴파일러 설계, 파싱, 정형 모델의 정형 검증 등의 중요한 요소다. 오토마타가 수학적으로 고찰, 결론 내린 내용은 알고리즘으로 표현하여 현대의 컴퓨터에게 적용하기도 한다. [컴퓨터에게 생각을 만들어 주기 : 알고리즘의 유래와 정의]

유용하셨다면 공감한번 꾹! 눌러주세요!