촘스키 위계 쉽게 이해하기: 정규·문맥자유·문맥의존·무제한 문법과 필요한 메모리

핵심 메시지

• 문자열을 만들어 내는 문법의 규칙 구조가, 그 언어를 인식하는 기계에 필요한 메모리의 양을 결정한다.
• 규칙을 느슨하게 풀수록 계산 능력이 한 단계씩 올라가며, 이를 네 겹의 동심원(촘스키 위계)으로 나타낼 수 있다.
• 정규 문법은 유한 상태 기계로 충분하지만, 개수를 무한정 세는 일은 하지 못한다.
• 문맥자유 문법은 스택(푸시다운 오토마타)으로 괄호·중첩 구조를 처리하고, 문맥의존 문법은 제한된 테이프로 세 쌍의 개수까지 맞춘다.
• 무제한 문법은 튜링 기계가 계산할 수 있는 모든 것을 포괄하며, 정지 문제 같은 결정 불가능한 문제까지 포함한다.

쉽게 이해하기

겉보기에 단순한 세 개의 문자열이 있다. 'AAAA'는 그저 개수를 세면 되고, 'AAABBB'는 A의 개수를 센 뒤 같은 수의 B와 맞춰야 하며, 'AAABBBCCC'는 세 개의 개수를 동시에 유지해야 한다. 흥미로운 점은 이것이 문자열 자체의 문제가 아니라, 그 문자열을 만들어 내는 '문법'의 문제라는 사실이다. 생성 규칙의 구조가 그 언어를 인식하는 데 필요한 메모리의 양을 정확히 결정한다.

가장 아래에는 가장 엄격한 정규 문법이 있다. 모든 규칙은 하나의 비단말 기호를 하나의 단말 기호로(뒤에 비단말이 하나 더 붙을 수 있음) 바꾼다. 문자열을 왼쪽에서 오른쪽으로만 키울 수 있고 양방향으로 동시에 늘릴 수는 없다. 이는 곧 유한 상태 기계에 대응하는데, 상태의 수가 유한하기 때문에 100개의 A 뒤에 정확히 100개의 B를 세는 것처럼 끝없이 커지는 수를 기억하지 못한다.

규칙을 조금 풀면 문맥자유 문법이 된다. 좌변은 여전히 하나의 비단말이지만 우변에는 단말과 비단말을 어떤 조합으로든 놓을 수 있다. 'S → SB' 같은 규칙은 양쪽으로 동시에 자라나 결국 개수가 맞는 A와 B를 만든다. 괄호 짝 맞추기, 중첩된 대괄호, 중첩 if 문 같은 프로그래밍 언어 구조가 모두 여기에 속하며, 이를 인식하려면 유한 상태 기계에 스택을 더한 푸시다운 오토마타가 필요하다.

한 단계 더 오르면 문맥의존 문법이다. 비단말은 주변 문맥이 맞을 때만(αAβ → αγβ) 치환된다. 이 작은 추가 능력만으로 'AAABBBCCC'처럼 세 종류를 같은 개수로 맞추는 일이 가능해지는데, 이는 어떤 문맥자유 문법으로도 할 수 없다. 이때의 인식기는 입력 길이를 넘지 못하는 테이프를 가진 튜링 기계, 즉 선형 유계 오토마타다.

사다리 맨 위의 무제한 문법에서는 좌변이 비단말을 하나라도 포함하는 어떤 문자열이든 될 수 있다. 이는 튜링 기계가 계산할 수 있는 모든 것, 곧 정지 문제처럼 결정 불가능한 문제까지 포함하는 전 영역이다. 결국 네 겹의 동심원이 그려진다. 중심의 3형부터 2형·1형을 거쳐 전체 공간인 0형까지, 원을 하나씩 넘을 때마다 '메모리 없음 → 스택 → 제한된 테이프 → 무한한 테이프'라는 새로운 기억이 생긴다. 촘스키는 1956년 자연어를 이해하기 위해 이 분류를 발표했고, 그것이 계산 이론 전체를 형성했다.

주요 인사이트

• 문법의 '표현력'과 그것을 인식하는 데 드는 '메모리'는 동전의 양면이다. 더 복잡한 패턴을 표현하려면 더 강력한 기억 장치가 필요하다.
• 프로그래밍 언어의 괄호·중첩 구조가 본질적으로 문맥자유라는 사실은, 파서가 왜 스택을 사용하는지를 설명해 준다.
• 'AAABBBCCC'처럼 세 종류를 동시에 같은 개수로 맞추는 패턴은 문맥자유의 한계를 넘어 문맥의존 문법을 요구한다.
• 무제한 문법이 정지 문제 같은 결정 불가능 영역까지 닿는다는 점은, 계산 가능성의 한계 자체가 문법의 표현력과 이어져 있음을 보여준다.
• 촘스키가 1956년 자연어를 이해하려고 만든 분류가 계산 이론 전체의 뼈대가 되었다는 점은, 언어와 계산이 얼마나 깊이 연결되어 있는지를 시사한다.

자주 묻는 질문