개념 정리 - (3) 형식 언어와 오토마타 편
우리가 배운 개념이 어디서 어떻게 쓰이는지 알아보자
오토마타는 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 분야이다. 오토마타에서 배운 것을 직접적으로 쓰게 되는 것은 형식 언어를 정의하는 관점에서 컴파일러에서 구분 분석을 하면서 추상 구문 트리를 생성할 때이고, 계산 능력을 가진 추상 기계를 논하는 관점에서 계산 이론적으로 P-NP 문제와도 연관성이 있다. 대개는 컴파일러를 위해 배우는 분야이다 보니 푸시 다운 오토마톤까지만 자세히 다루고 그 이상의 이론은 잘 다루지 않는다. 이 글에서도 컴파일러에서 필요한 부분 위주로 설명하겠다. 참고로 오토마톤(automaton)을 복수형으로 오토마타(automata)라고 한다.
촘스키 위계
먼저 앞으로 다루게 될 내용의 전체 맥락을 소개하고자 한다. 촘스키 언어 계층은 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 귀납적 가산 언어 4 계층으로 형식 언어를 규정한다. 각 언어 계층을 인식할 수 있는 오토마톤을 차례로 배워나가는 것이 오토마타 강의에서의 흐름이다. 유한 상태 기계로 정규 언어를, 푸시 다운 오토마톤으로 문맥 자유 언어를, 선형 구속형 비결정성 튜링 기계로 문맥 의존 언어를, 튜링 기계로 귀납적 가산 언어를 인식할 수 있다. 각 계층의 언어는 상위 계층 언어의 부분 집합이기 때문에 정규 언어로는 문맥 자유 언어를 표현할 수 없지만 문맥 자유 언어로는 정규 언어를 표현할 수 있고, 보다 상위 계층의 언어를 하위 계층의 오토마톤이 인식할 수 없다.
출처 : http://rstb.royalsocietypublishing.org/content/367/1598/1933형식 언어와 생성 규칙, 연산
형식 언어는 유한한 종류의 문자로 이루어진 유한한 길이의 문자열의 집합을 말한다. 해당 언어를 이루는 문자들의 집합에 대한 클레이니 스타 연산 결과 집합의 부분 집합으로 볼 수 있는데, 좀 더 자세한 정의는 위키백과를 참고. 당연히 아무런 의미 없는 부분 집합보다는 우리가 원하는 규칙대로 만들어지는 언어에 더 관심 있다.
정규 언어의 예로 이메일 주소를 나타내는 언어를 생각해볼 수 있다. 이메일 주소의 문자열 규칙은 알파벳과 숫자로 이루어진 문자열 뒤에 골뱅이 표가 오고, 도메인 문자열이 온다. 이러한 생성 규칙을 함축한 것이 정규 표현식으로써 이메일 주소에 대한 정규 표현식은 "^[0-9a-zA-Z_\-]+@[.0-9a-zA-Z_\-]+$"와 같은 것이 해당된다. 엄밀히 말해서 정규 표현식은 편의를 위해 기본적인 생성 규칙 외의 추가적인 연산자들이 존재하지만, 기본 연산을 통해 추가 연산을 구현 가능하기 때문에 언어 위계 상으로는 동일하다.
또한, 언어에 대한 연산이 존재하는데, 언어를 집합으로 보면서 일반적인 교집합, 합집합, 여집합 연산이 가능하며 클레이니 스타 연산, 접합(concatenation) 연산이 있다.
정규 언어
유한 상태 기계는 한 번에 오로지 하나의 상태만을 가지게 되며, 현재 상태(Current State)란 임의의 주어진 시간의 상태를 칭한다. 이러한 기계는 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. DFA(Deterministic Finite Automata), NFA(Nondeterminstic Finite Automata)가 유한 상태 기계에 속하는 오토마톤이다. 모든 NFA는 DFA로 변환 가능하다는 것이 증명되어 있다.
유한 상태 기계로 인식 가능한 언어가 정규 언어(Regular Language)이고, 우리가 흔히 알고 있는 정규 표현식(Regular Expression)도 정규 언어에서 파생됐다. 앞서 언어를 인식하고자 할 때 하위 계층의 오토마톤으로는 상위 계층의 언어를 인식할 수 없다고 하였기 때문에 우리가 컴파일하고자 하는 프로그래밍 언어에 대해 유한 상태 기계가 쓸모없어 보이지만 그렇지 않다. 문맥 자유 문법을 인식하는 상태 기계를 만들 수는 없지만 파싱을 효율적으로 수행하는 알고리즘을 구현하기 위한 도구를 만들기 위해 유한 상태 기계가 활용된다.
문맥 자유 언어와 펌핑 보조 정리
정규 언어의 표현력으로는 프로그래밍 언어를 정의하기 어렵다. 예를 들어 단순한 덧셈 수식을 언어로 표현하기 위해서는 숫자가 나타난 뒤 덧셈 기호가 오고 다시 숫자가 나타나야만 한다는 생성 규칙을 정의할 수 있어야 한다. 이 경우 이전의 상태로 돌아갈 수 있어야만 한다. 이러한 계산 능력을 갖춘 기계가 바로 푸시 다운 오토마타이다. 푸시 다운 오토마타는 스택을 갖고 있기 때문에 다음 상태를 스택이 푸시(push)하여 새로운 상태로 전이된 후, 스택을 팝(pop)하여 이전 상태로 돌아갈 수 있다.
출처 : 위키백과그렇다면 어떤 언어가 주어졌을 때 이것이 정규 언어인지, 문맥 자유 언어, 문맥 자유 언어를 초월하는 언어인지 어떻게 알 수 있을까? 펌핑 보조 정리가 그 해답을 제시한다. 펌핑 보조 정리는 어떤 언어가 특정 형식 언어에 속하기 위한 필요조건이지 충분조건은 아니다. 하지만, 주어진 언어가 특정 펌핑 보조 정리를 성립시키지 못한다는 것을 보임으로써 그에 해당하는 형식 언어에 속하지 않음을 보일 수는 있다. 펌핑 보조 정리의 증명과 활용은 다음 문서에 잘 정리되어 있다.
촘스키 정규 형식과 멤버십 알고리즘
문맥 자유 언어를 공부할 때면 항상 촘스키 정규 형식이 중요한 개념으로 등장한다. 촘스키 정규 형식의 의의는 모든 문맥 자유 언어가 촘스키 정규 형식으로 변환 가능하고 CYK 알고리즘이 촘스키 정규 형식을 기반으로 수행된다는 것에 있다. 어떤 문자열이 이미 정의한 언어에 포함되는지 확인하는 알고리즘을 멤버십 알고리즘이라고 하는데, CYK 알고리즘은 현존하는 가장 빠른(O(n^3)) 멤버십 알고리즘이다.
아쉽게도 O(n^3) 시간 복잡도로는 만족스러운 컴파일 속도를 낼 수가 없다. 그렇기 때문에 실제 프로그래밍 언어를 정의하는 문법에서는 단순 문맥 자유 문법보다 더 제약을 추가하여 문법을 정의하고 있다. 이렇게 함으로써 CYK 알고리즘보다 더 빠른 멤버십 알고리즘을 적용할 수 있다. 예를 들면 SLR(1) 파싱 알고리즘을 적용할 수 있는 SLR(1) 문법은 다음 조건을 만족해야 한다.
For any reducible rule A → a • Xb in state s (where X is some terminal), there must not exist some irreducible rule, B → a • in the same state s such that the follow set of B contains the terminal X. In more formal terms, the intersection of set containing the terminal X and the follow set of B must be empty. Violation of this rule is a Shift-Reduce Conflict.
For any two complete items A → a • and B → b • in s, Follow(A) and Follow(B) are disjoint (their intersection is the empty set). Violation of this rule is a Reduce-Reduce Conflict.
SLR(1) 문법으로 만들어진 언어를 SLR(1) 언어라고 하고, SLR(1) 문법은 LR(0) 문법의 상위 집합이며 LALR(1) 문법과 LR(1) 문법의 하위 집합이다.
튜링 기계와 문제
우리가 흔히 알고 있는 그 튜링 머신이다. 튜링 기계의 좀 더 자세한 내용은 위키 백과를 참고. 현존하는 컴퓨터로 계산할 수 있는 것은 튜링 기계로도 가능하다. 말하자면 튜링 기계는 컴퓨터와 동일한 수준의 계산 능력을 가진 기계이기 때문에 튜링 기계에서 풀 수 없는 문제는 컴퓨터로도 풀 수 없는 문제라고 생각할 수 있다. 이러한 문제의 예로는 정지 문제가 있다. 정지 문제는 결정 문제의 일종인데, 문제라는 것에 대해 좀 더 알아보자.
결정 문제는 어떤 형식 체계에서 예, 아니오로 답이 있는 문제이다. 예를 들어 x가 y로 나누어지는가는 x와 y 값에 따라 예 혹은 아니오로 결정될 수 있다. 결정 문제를 풀 수 있는 알고리즘이 존재한다면 그 문제를 결정 가능한 문제라고 한다. 정지 문제는 처음으로 증명된 결정 불가능한 문제이다.
컴퓨터 공부를 시작하면서 P-NP 문제에 대해 들어봤을 것이다. P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이고, NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. NP 문제 중 하나인 부분집합 합 문제는 어떤 부분집합이 주어졌을 때 원소의 합이 0인지 확인하는 것은 다항 시간에 계산 가능하지만, 그러한 부분집합을 구하는 것은 다항 시간 내에 계산 가능한 알고리즘이 알려져 있지 않다.
NP 난해(NP-Hard)는 적어도 모든 NP 문제만큼은 어려운 문제 집합이다. NP 난해 문제는 결정 가능한 문제를 넘어서 결정 불가능한 문제까지도 영역이 뻗어져 있다. NP 완전(NP-Complete) 문제는 NP 집합에 속한 결정 문제 중 가장 어려운 문제 집합인데, NP 난해 문제와 NP 문제의 교집합이기도 하다. 모든 NP 문제를 NP 완전 문제로 다항 시간 내에 환산할 수 있기 때문에 NP 완전 문제 중 하나라도 다항 시간 내에 풀린다면 모든 NP 문제가 다항 시간 내에 풀릴 수 있게 된다.
출처 : 위키백과지금까지 학부 수준 오토마타 이론에서 다루는 내용들에 대해 알아보았다. 형식 언어를 정의하는 것과 계산 능력을 가진 추상 기계를 다루는 관점에서 다루는 내용들이었다. 이 편으로 수학적 기초와 계산 이론을 다루는 것을 끝내고 알고리즘과 자료구조로 넘어간다. 다음 편에서는 자료구조에 대해 다뤄보겠다.
