[개념쌓기] 오토마타 - 1

요즘 귀감이 되고 있는 분과 얘기를 나누다보니, 무엇을 하고 싶은 지에 대한 얘기가 나왔다. 이야기가 흘러흘러 가다보니, 기술동향에 대해 얘기를 하게 되고 어쩌구 저쩌구 하다보니 오토마타에 대해서는 알고 있는지에 대한 물음이 왔다. 영화 '크리에이터' 나 게임 "니어 오토마타"를 유튜버들이 한다고 하는 것에서만 들어봤지. 이것에 대해 궁금증을 가진 적이 없었다.  문득 그래서 이게 뭐지 라는 생각이 들었다. 

 

이분이 현재 종사하시는 분야는 다르신데, 에 대한 정보가 엄청나셔서 쪼메 므싯어 보였다.

 

---

🔔오토마타 이론(Automata Theory)

: 계산 능력이 있는 추상 기계와 그 기계를 통해 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야 

: 추상적인 연산 장치(오토마톤)가 계산할 수 있는 것과 그렇지 않은 것에 대한 이론

   => 형식언어 이론과 컴퓨터 과학에서 중요한 개념 중 하나

 

오토마타는 오토마톤의 복수형으로, 추상적인 연산 장치 또는 '기계(machine)'이다.

계산 능력을 갖춘 것이지만, 반드시 물리적인 하드웨어를 필요로 하진 않는다.

 

오토마톤의 예시 중 하나, 스위치다.

구조의 간단성에 push를 따라가면 on/off의 변화를 한눈에 알 수 있다.

---

앞서 언급했던 것처럼 오토마타는 형식 언어를 어느 정도 이해해야한다.

 

🔔형식 언어?

수학, 컴퓨터 과학, 언어학에서 형식 언어는 특정 법칙에 따라 적절히 구성된 문자열들의 집합을 말한다.

수학기초론, 언어학, 정보 이론의 핵심적 개념으로 계산가능성 이론과 밀접한 관련이 있다.   - 위키백과-

 

 

오토마타는 연산 능력 덕분에 목적에 따라 특정 입력에 대해 의도된 출력, 혹은 결과물을 내놓도록 설계된다.

계산기를 예로 들면, 계산기의 목적에 따라 1+1을 입력하면 답을 도출해내듯, 언어도 이렇게 가능할까?

 

인간은 의사소통을 할 때 언어를 사용하는데, 이를 자연어라고 한다.

자연어는 인간의 뇌에 적합한 언어이기에, 아무리 연산 능력을 갖춘 오토마타라 하더라도 자연어의 형태를 이해하는 것이 매우 어려웠다. 인간들끼리의 대화에서도 이해가 안되는 경우가 있는데, 기계에게는 더욱 어려웠던 것이다.

 

위에서 언급한 형식 언어는 인간의 언어를 말하는 것이 아닌, 언어가 가진 특징을 보편화/추상화하며 수학적으로 형식화한 인공적인 언어다. 지금 말하는 형식 언어는 항상 정해진 형식을 따르기에 기계도 오해없이 항상 제대로 이해가 가능하다.

 

영어의 영문법을 형식적으로 배우듯이, 형식 언어도 형식 문법이 있다.

=> 생성 문법 : 형식 문법에서 해당 형식 언어의 문자열을 생성

=> 해석 문법 : 어떤 문자열이 특정 언어에 포함되는지를 판단

 

🤔형식 언어와 오토마타와의 연관성

오토마타는 인간이 사용하는 자연어와는 달라도, 형식 언어라는 언어를 이해 가능하다.

오토마타의 역할은 해석 문법과 관련이 있는데, 오토마톤이 문자열을 입력받아 특정 언어에 포함되는지 판단하는 인식기 역할을 할 수 있기 때문이다.

 

형식 언어에도 여러 종류가 있고, 오토마타의 성능에 따라 계산 가능한 언어를 범주화할 수 있다.

이는 처음 발견한 노엄 촘스키의 이름을 따서 '촘스키 위계'라고 부른다.

 

✔  촘스키 위계

형식 언어를 생성하는 형식 문법의 클래스 사이의 위계, 노엄 촘스키가 1956년에 제시

 

예를 들면, 어떤 스펙을 가진 오토마타는 입력받은 문자열이 어떤 형식 언어에 속하는 문자열인지, 아닌지를 판별할 수 있다라는 계산 가능성 이론이다.

 

다음 글에서 먼저 정리할 오토마타의 계층은 유한 오토마타로 촘스키 위계에 따르면, 정규 언어를 인식가능한 오토마타이다. 가장 좁은 범위의 형식 언어를 인식할 수 있는 매우 제한적인 스펙의 오토마타이다.

 

최근에는 이론적인 부분에 국한되어 정리를 진행했었는데, 이번 오토마타에서는 이론적인 부분을 떠나서 조금 더 딥하게 공부해보려고 한다.

그럼 이만 안녕 요호호호호홓