오토마타 이론과 형식 언어

오토마타 이론(Automata Theory)이란?

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

추상 기계를 오토마타(Automata, 복수형) 또는 오토마톤(Automatnon, 단수형) 이라고 한다.

기계는 일반적으로 유한한 상태의 집합을 갖고 있다. 유한한 개수의 상태를 가질 수 있는 기계를 유한 상태 기계(finite-state machine), 오토마톤을 유한 오토마톤(finite automaton)이라 한다. 기계는 입력에 따라 현재 상태에서 다음 상태로 전이하며 출력을 내놓는다. 이는 계산 문제를 해결할 능력과 같다.

특정한 유한 오토마톤은 어떤 사건(event)에 의해 현재 상태(current state)에서 다른 상태로 변화할 수 있으며 이를 전이(Transition)라 한다.

이 그림은 간단한 ON/OFF 스위치를 오토마톤으로 표현한 것이다.

스위치는 ON 또는 OFF인 상태를 가질 수 있으며(유한한 상태의 집합), 입력(여기선 push)에 따라 다른 상태로 전이될 수 있다.

오토마타 이론은 계산 능력이 있는 추상 기계를 다룬다는 관점에서 P-NP 문제와도 관련이 있다.

---

형식 언어(Formal Language)

아무리 뛰어난 오토마타라고 해도 인간의 언어인 자연어를 이해하는 일은 매우 어렵다. 하지만 애매모호한 자연어를 일정한 규칙을 가지고 있는 어떤 형식 언어로 만들 수 있다면 자연어를 계산기가 처리할 수 있을 것이다.

형식 언어란, 특정한 법칙들에 따라 구성된 문자열들의 집합을 말한다. 미국의 언어학자 촘스키(Avram Noam Chomsky)의 이론에 따르면 형식 언어에는 다음 네 가지 유형이 있다.

촘스키 위계	형식 문법	형식 언어	오토마타
0유형	무제약 문법	재귀 열거 언어	튜링 기계
1유형	문맥 의존 문법	문맥 의존 언어	선형유한 오토마타
2유형	문맥 자유 문법	문맥 자유 언어	내리누름 오토마타
3유형	정규 문법	정규 언어	유한 상태 기계

촘스키 위계(Chomsky hierarchy)에서 가장 간단한 오토마타는 유한 상태 기계이다. 이 오토마타는 정규 문법을 따르는 정규 언어를 인식할 수 있다. 표에서 위로 갈수록 복잡하고 모호한 언어를 계산할 수 있다.

본 세미나 막바지에는 문맥 자유 문법(CFG, context free grammar)을 적용한 형식 언어 분석 알고리즘인 CYK 알고리즘을 이해해볼 것이다.

노엄 촘스키(1928~)

---

형식 언어의 구성 요소

심볼(Symbol)

가장 기본적인 단위. 한국어에서는 ㄱ, ㄴ, ㅏ, ㅑ... 등이 있다. 영어에서는 a, b... 등이 있다.

알파벳(Alphabet)

언어에서 사용하는 문자로 이루어진 공집합이 아니면서 유한한 집합이다.
영어 알파벳 의 예시 : $$ \Sigma=\{A, B, ..., y, z\} $$
이처럼 관례적으로 알파벳 집합을 표현하기 위해 시그마 기호를 쓴다.

문자열(String 또는 word)

해당 언어의 알파벳에 속한 심볼들로 이루어진 유한한 길이의 열.
영어 문자열 예시 : {hidden}, {legacy}, {aaaaaa}, {qwer}
빈 문자열 {}도 영어의 문자열이 될 수 있다. 이는 특별히 \(\epsilon\) (epsilon) 기호를 써서 표현한다.

 

알파벳으로 이루어진 모든 문자열의 집합은 \(\Sigma{}^{*}\)로 쓴다. 이때 별표는 클레이니 스타이며, 시그마의 클레이니 스타 또는 간단히 시그마 스타라고 읽는다. 정의에 따라 시그마 스타는 당연히 무한집합이다.

* 클레이니 스타의 정의(더보기 클릭!)

wikipedia

따라서 언어는 어떤 \(\Sigma^{*}\)의 부분집합이다.

---

언어의 연산

언어 \(L_1=\{a, b, c\}\), \(L_1=\{a, d\}\) 에 대하여,

• \(L_1\)과 \(L_2\)의 연쇄는 \(L_1\)의 문자열 \(v\)와 \(L_2\)의 문자열 \(w\)를 연쇄시켜 만든 단어들의 집합이다. 표기 : \( L_1 \cdot L_2 \) 또는 \(L_1L_2\)
• \(L_1\)과 \(L_2\)의 교집합은 \(L_1\)과 \(L_2\)에 동시에 속하는 문자열들의 집합이다. 표기 : \( L_1 \cap L_2 = \{a\} \)
• \(L_1\)과 \(L_2\)의 합집합은 \(L_1\) 또는 \(L_2\)에 속하는 문자열들의 집합이다. 표기 : \( L_1 \cup L_2 = \{a, b, c, d\} \)

 

 

---

오토마타와 형식 언어

우리가 하고 싶은 것은 구문 분석이다. 다르게 표현하면, 알려진 문법 규칙을 바탕으로 주어진 문자열 또는 구가 해당 언어의 구가 될 수 있는지 판단하는 과정이다.

어떤 문장이 주어졌다고 생각해보자. 이 문장이 해당 언어의 문장인지 확인하기 위해 해당 언어가 생성할 수 있는 모든 문장과 대조하는 것은 불가능한 일이다. 이 때 유한 오토마타를 사용하면 주어진 문장이 정규 언어가 생성할 수 있는 문장인지 확인할 수 있다. 유한 오토마타는 상태(state)로 입력을 기억하는데, 이 기억 공간의 한계 때문에 촘스키 위계에서 가장 단순한 언어인 정규 언어(regular language)까지만 이해할 수 있다. 

마지막 장에서 다룰 CYK 알고리즘에서는 문맥 자유 언어를 가정한다. 이때 문맥 자유 언어의 예로 \(L=\{a^nb^n \,|\, n\geq1\}\)을 들 수 있다. \(L\)을 설명하는 문맥 자유 문법으로 \(S\to aSb \, | \, ab \) 를 들 수 있다. 이 언어는 정규 언어가 아니다. 따라서 유한 오토마타로 인식할 수 없다. 왜냐고?

 * 직관적인 이유 : 유한 상태 오토마타는 기억할 수 있는 a와 b의 개수가 한정적이므로 무한한 a와 b를 기억할 수 없음.