촘스키 위계(Chomsky hierarchy)

언어를 수학의 대상으로 다루는 형식 언어⁠(formal language)⁠ 이론에서 언어란 어떤 글자들(알파벳 Σ)로 만든 문자열들의 집합⁠(set)⁠입니다. '짝수 개의 a', 'a 몇 개 다음에 같은 수의 b', '멈추는 프로그램의 소스 코드' 모두 언어입니다. 문법은 이런 집합을 유한한 규칙으로 적는 방법이고, 1950년대 후반 노엄 촘스키는 규칙의 모양을 얼마나 제한하느냐에 따라 문법을 네 층으로 나누었습니다. 규칙이 자유로울수록 더 많은 언어를 적을 수 있고, 그 언어를 알아보는 기계에게는 더 많은 기억이 필요합니다.

그림의 점을 누르거나 여기서 언어를 고르세요: . 이 언어가 사는 층은 입니다.

층을 가르는 것은 기억입니다. 가장 안쪽의 정규 언어⁠(regular language)⁠는 상태만 기억하는 유한 오토마톤이 알아보고, 정규 표현식⁠(regular expression)⁠으로 적을 수 있습니다. 여기에 스택(접시 더미처럼 맨 위에만 넣고 꺼낼 수 있는 기억 장치) 하나를 더하면 문맥 자유 문법⁠(context-free grammar)⁠의 언어를 알아보는 푸시다운 오토마톤이 됩니다. 입력이 적힌 칸만큼의 테이프를 읽고 쓸 수 있게 하면 선형 유계 오토마톤, 테이프에 끝이 없으면 튜링 기계가 됩니다. 여기서 기계들은 갈림길에서 여러 길을 동시에 시도할 수 있는(비결정적) 기계로 봅니다. 유한 오토마톤과 튜링 기계에서는 갈림길이 힘을 늘리지 않지만, 푸시다운 오토마톤에서는 늘리고, 선형 유계 오토마톤에서는 늘리는지 아직 모릅니다.

한 층이 바로 아래 층보다 정말 큰지는 따로 증명해야 합니다. aⁿbⁿ이 정규가 아니라는 증명에는 펌핑 보조정리⁠(pumping lemma)⁠를 씁니다. 상태가 k개인 기계가 k글자 이상을 읽으면 비둘기집 원리⁠(pigeonhole principle)⁠에 따라 같은 상태를 두 번 지나고, 그 사이에 읽은 조각은 몇 번을 되풀이해도 기계의 판정이 바뀌지 않습니다. $a^k b^k$를 읽으면 처음 k글자, 곧 a들 안에서 이미 같은 상태를 두 번 지나므로 되풀이할 조각은 a로만 되어 있습니다. 이 조각을 한 번 더 넣으면 a가 b보다 많아지는데도 받아들여지니, 그런 기계는 있을 수 없습니다. 층마다 비슷한 보조정리⁠(lemma)⁠가 있습니다.

가장 바깥 층 너머에도 언어가 있습니다. 문법은 유한한 글자로 적히니 모두 합쳐도 가산 개입니다. 반면 언어는 Σ*(Σ의 글자로 만들 수 있는 모든 유한 문자열의 집합)의 부분집합⁠(subset)⁠이라 멱집합⁠(power set)⁠만큼, 곧 대각선 논법⁠(diagonal argument)⁠에 따라 셀 수 없이 많습니다. 따라서 어떤 문법으로도 적을 수 없는 언어가 셀 수 없이 많고, 문법으로 적을 수 있는 언어는 가산개뿐입니다. 가장 바깥 층인 재귀 열거⁠(recursively enumerable)⁠ 언어는 '입력이 그 언어에 속하면 언젠가 멈춰 받아들이는' 튜링 기계가 있는 언어이고, 제한 없는 문법이 적는 언어와 정확히 같습니다. 구체적인 예가 정지 문제⁠(halting problem)⁠에서 나옵니다. 멈추는 프로그램들의 코드를 모은 언어는 재귀 열거이지만(돌려 보다가 멈추면 받아들이면 됩니다), 멈추지 않는 프로그램들의 언어는 가장 바깥 층에도 들지 못합니다. 또 재귀 열거 층 안에는 튜링 기계가 언제나 멈추며 '예·아니요'를 답하는, 곧 결정 가능⁠(decidable)⁠한 언어들의 층이 따로 있고, 문맥 의존 언어⁠(context-sensitive language)⁠는 모두 그 안에 들어갑니다. '기계적으로 계산할 수 있는 것'을 가장 바깥 층의 기계, 곧 튜링 기계로 정의해도 된다는 주장이 처치–튜링 논제⁠(Church–Turing thesis)⁠입니다. 증명된 정리가 아니라 증거로 받아들이는 논제입니다.

자연어는 어디쯤일까요? 촘스키는 영어가 유한 상태 모형으로는 설명되지 않는다고 주장했고, 앞 단어 몇 개만 보는 n-그램⁠(n-gram)⁠ 모형이 바로 그런 유한 상태 모형입니다. 1985년 미국의 컴퓨터 언어학자 스튜어트 시버는 스위스 독일어의 교차 의존⁠(cross-serial dependency)⁠ 구문을 들어 자연어가 문맥 자유 층도 조금 넘어선다고 논증했습니다. 스위스 독일어에서는 '우리가 한스가 집을 칠하도록 도왔다'를 '우리 한스에게 집을 도왔다 칠하다' 순서로 말할 수 있습니다. 명사들이 먼저 나오고 동사들이 같은 순서로 뒤따라서, 첫 명사는 첫 동사와, 둘째 명사는 둘째 동사와 짝을 이룹니다. 짝들이 괄호처럼 안쪽으로 겹치지 않고 서로 엇갈리는 것인데, 형식 언어로 쓰면 $a^m b^n c^m d^n$ 모양이라 문맥 자유 문법으로는 적을 수 없습니다. 그래서 지금은 흔히 '문맥 자유보다 약간 강한' 층에 자연어가 있다고 봅니다.

이어지는 곳. 사람이 쓴 프로그램 소스 코드를 기계가 실행할 명령으로 옮기는 컴파일러⁠(compiler)⁠는 이 위계를 그대로 씁니다. 소스 코드를 낱말로 자르는 단계는 정규 표현식, 낱말을 그래프인 구문 트리⁠(parse tree)⁠로 묶는 단계는 문맥 자유 문법입니다. 층마다 '알아볼 수 있는가'뿐 아니라 '얼마나 빨리 알아볼 수 있는가'도 물을 수 있고, 이렇게 계산에 드는 시간을 따지는 물음의 대표가 P 대 NP 문제⁠(P versus NP problem)⁠입니다. 가장 바깥 층의 기계인 튜링 기계와 같은 힘을 기계 대신 함수⁠(function)⁠로 적은 것이 람다 계산⁠(lambda calculus)⁠입니다.