[Automata] Automata란?
Automata란?
포스트 난이도: HOO_Junior
[Notice] 포스트 난이도에 대한 설명
안녕하세요, HOOAI의 Henry입니다. Bro들의 질문에 대한 내용을 우선적으로 포스팅이 되다 보니 각각의 포스트에 대한 난이도가 달라서 난이도에 대한 부분을 작성하면 좋겠다는 의견을 들었습니다
whoishoo.tistory.com
# Automata Theory
오토마타 이론(Automata theory)은 현재 Computing에 있어서 Algorithms들에 대한 이론적인 부분이라고 알려져 있다.
사실 오토마타는 컴퓨터가 발전하고 나온 컴퓨터 알고리즘 이론이라기보다는 기존부터 있던 알고리즘 이론이다.
알고리즘이라는 것 자체가 기원전 2500년때 부터 이미 사용되어오고 있다는 점에서 오토마타 이론은 오래전부터 있었지만 컴퓨팅 알고리즘에 활용되고 발전해왔다고 볼 수 있다.
오토마타 이론이 컴퓨팅 알고리즘에 활용되는 큰 이유 중 하나는 추상적인 요소를 계산적인 요소로 바꿔서 이해하고 계산하기 위해서는 알고리즘이 필요하다.
오토마타 이론은 이러한 추상적인 문제를 계산할 수 있는 상태로 만들어 알고리즘화를 할 수 있다는 점에서 컴퓨팅 과정에서 적용하여 사용하게 되었다.
# Digitial computers에 필요한 효율성
앞서도 이야기해왔지만 computer의 발전이라 함은 하드웨어적 발전도 있지만 사실상 산출되는 결과의 처리 속도와 정확성이 중요하다.
한마디로 원하는 값에 대한 결과가 신속하고 정확하게 산출되기 원한다는 것이다.
그렇다 보니 제한된 물리적인 방식에서 효율성을 극대화하기 위해서는 알고리즘과 같은 처리 방식 자체의 변화를 줌으로써 효율성의 극대화를 가져올 수 있었다.
# 오토마타와 알고리즘
오토마타(Automata)는 알고리즘을 구현하고 정의하는 데 필요한 아주 기본적인 표현 방식이다.
알고리즘을 정의하는데 있어서 Automata가 정해준 방식대로 표현하고 나타내는 걸 의미한다.
그렇기에 기존에 알고리즘화가 되지 않은 추상적인 문제에 대하여 알고리즘화로 정의하는 것 자체를 오토마타를 통해서 한다고 볼 수 있다.
# 오토마타가 알고리즘 구현에 필요한가?
솔직히 간단한 문제들만 살펴보면 알고리즘 자체의 정의가 필요한가 싶은 의문이 들 수도 있다.
하지만 우선적으로 추상적인 문제를 알고리즘화를 한다는 것 자체가 어려운 일이다.
알고리즘에 대한 연구와 개발은 지금까지도 지속적으로 이루어지고 발전해오고 있다.
그럼에도 불구하고 모든 문제가 computing이 가능한 것이 아니다.
복잡한 문제일수록 알고리즘화를 하기 위해서 각각의 상태를 정의하여 정리하고 그것을 계산적 문제로 만들어주는 일을 어렵다.
따라서 오토마타에서 주어진 방식을 토대로 추상적 문제를 계산적 문제로 전환하기 위한 기본적인 과정을 거치게 된다.
# 오토마타를 왜 배워야 하는가?
사실 프로그램을 당장 개발하는데 오토마타를 몰라도 된다.
심지어 개발자 중에서는 오토마타가 무엇인지도 모르는 경우도 있다.
그럼에도 불구하고 오토마타 이론에 대해서 알아야 하는 이유는 프로그램 개발에 있어서 직접적으로 사용하기 때문이다.
예를 들면 digital circuits, compiler 과정 중에서도 Automata의 regular expressions을 사용하고 있기에 개발자로서 이해하기 위해서는 알아두어야 하는 게 필자가 생각하는 실질적인 이유다.
또한 필자가 오토마타 이론을 배우고 정리하면서 느낀 점은 알고리즘의 대한 이해도를 높이는데 큰 도움이 된다는 점이다.
사실 첫번째 말한 이유도 와닿지 않을 수 있지만 두 번째 이야기한 알고리즘을 분석하고 이해하는데 도움이 되는 건 사실이다.
오토마타는 사실상 이론적인 부분인 컴퓨팅 알고리즘의 기초 문법이자 기본 상식이라고 볼 수 있다.
마치 한국말을 하는데 문법을 몰라도 한국말을 하는데 지장이 없듯이 오토마타를 몰라도 프로그래밍을 하는데 당장의 지장은 없을 순 있다.
하지만 오토마타 이론을 이해하면서 어렵게만 느껴지던 알고리즘을 분석하고 이해하는데 도움이 되며, 이를 기반으로 알고리즘을 개발에 활용하는데 도움이 된다는 점에서 개발자라면 기본적으로 알아두어야 할 개념이라고 생각한다.
한마디로 Automat theory를 안다는 것은 Heuristic thinking 뿐만 아니라 Precise thinking이 가능해진다는 것이다.