[한국공공정책신문=김유리 기자]
◇ 유한 오토머턴의 개념
유한 오토머턴(finite automaton)이란 유한개의 상태와 전이와 동작의 조합으로 이루어진 수학적 모델이다. 오토머톤은 그리스어의 ‘자동으로 움직이는 것’에서 유래했으며, 기계장치 인형이나 동물을 의미한다. 어떤 목적에 맞는 복잡한 동작을 하는 기계를 가리키며, 예컨대, 자동판매기ㆍ로봇ㆍ계산기 등을 포함한다. 전환하여 입력(정보)과 출력(응답ㆍ동작) 사이에 명확한 함수관계가 있으며, 입력에 대한 인식과 판단의 기구와 적절한 출력을 자동으로 갖는 수학적 모델을 의미한다.
◇ 유한 오토머턴의 종류
유한 오토머톤에는 다음의 종류가 있다. ① 억셉터 리코그나이저(accept recognize), ② 트랜스듀서(transducer)이다. 이와 같이 2종류가 있는데, ①에서는 입력을 수용ㆍ이해하고, 외계에 결과를 알리기 위해 상태를 이용하는 반면, ②에서는 주어진 입력과 동작을 수반하는 상태를 바탕으로 출력을 생성한다.
◇ 유한 오토머턴의 노드와 엣지
유한 오토머톤은 노드(node, 절)와 엣지(edge, 화살표)로 이루어진 상태 도면을 이용해 표시된다. 노드는 상태, 엣지는 전이를 각각 나타낸다. 유한 개의 입력 기호가 정해져 현재 내부 상태와 입력 기호에 따라 다음 순간에 출력과 내부 상태가 결정된다. 모든 입력을 다 읽었을 때 수리 상태에 있으면 그 입력을 수리하고, 수리 상태가 아니면 입력을 거부한다.
◇ DFA와 NFA
다른 구분에서는 하나의 입력 기호에 대해 전환 목적지가 유일하게 결정하는 ‘결정성 유한 오토머톤’(DFA)과 하나의 입력 기호에 대해 전환 목적지가 여러 개 존재하는 ‘비결정성 유한 오토머톤’(NFA)으로 나눈다. 모든 NFA(비결정성 유한 오토머톤)은 등가 DFA(결정성 유한 오토머톤)으로 변환이 가능하다.
◇ 오토머톤의 정규언어
유한 오토머톤은 그 성질에서 문자열을 인식할 수 있으며, 하나의 유한 오토머톤이 주어지면 수리되는 문자열의 한 집합이 정해진다. 수용되는 문자열의 집합을 정규집합, 문자열의 집합을 하나의 문자열로 표현하는 방법을 ‘정규 표현’이라고 각각 부른다. 정규 표현을 사용하면 복잡한 문자열 검색이 효율적이다. ‘정규 문법’에서 생성되어 정규 표현으로 기술할 수 있으며 유한 오토머톤으로 수리할 수 있는 언어를 ‘정규 언어’라고 부른다.
◇ 푸시다운 오토머톤
유한 오토머톤에 특별한 기억 장치(스택)를 붙인 것을 ‘푸시다운 오토머톤(PDA)’이라고 한다. PDA는 회귀적인 구조를 기술할 수 있으며, 정규 표현보다 더 강력한 표현력을 가진 정규 언어(문맥 자유 언어)를 인식할 수 있다. 유한 오토머톤은 디지털 회로ㆍ프로그램ㆍ반도체ㆍ통신 프로토콜의 설계 등 공학계 외에, 신경계나 자연 언어의 문법의 모델화 등에 응용되고 있다.
이규철 / 법학박사(상법)
∙ AI·GPT, SDGs&ESG 코치 및 강사
∙ 100세대학 크리에이터 및 칼럼니스트
∙ 생성AI와 챗GPT, SDGs·ESG경영전략,
글로벌 MBAtoCEO, 리더의 필승전략,
100세대학 행복디자인 매뉴얼 등 27권
∙ 일본(와세다대),중국(복단대·화동정법대)
){kind=small}
){kind=small}
){kind=small}
){kind=small}