촘스키 위계 (Chomsky hierarchy)
쉽게 풀면
촘스키 위계는 '어떤 언어(문자열 집합)를 표현하려면 얼마나 강력한 문법이 필요한가'를 기준으로 언어들을 네 단계로 나눈 분류 체계다. 가장 단순한 정규 언어는 유한 오토마타로, 그다음 문맥 자유 언어는 푸시다운 오토마타(스택 하나)로, 문맥 의존 언어는 제한된 튜링 기계로, 가장 강력한 재귀 열거 가능 언어는 일반적인 튜링 기계로 인식할 수 있다. 이 위계는 각 단계가 그 이전 단계를 포함하는 포함 관계를 이루며, 계산 모델의 표현력과 언어의 복잡성을 연결짓는 핵심 이론이다.
왜 중요한가
촘스키 위계는 어떤 문제를 풀기 위해 최소한으로 필요한 계산 모델이 무엇인지를 알려주기 때문에, 프로그래밍 언어의 문법 설계나 컴파일러의 파서 구조를 정할 때 근거로 쓰인다. 자연어 처리 분야에서는 실제 자연어의 구문 구조가 어느 단계의 표현력을 필요로 하는지 논의할 때 자주 인용되며, 최근에는 신경망 기반 시퀀스 모델(RNN, 트랜스포머 등)이 어떤 형식 언어 클래스를 학습하거나 인식할 수 있는지를 촘스키 위계 틀로 분석하는 연구도 활발하다. 이처럼 이론 전산학, 언어학, 최근의 딥러닝 표현력 분석까지 폭넓게 걸쳐 있어 여러 하위분야 논문에서 공통된 준거로 등장한다.
논문에서는 이렇게 쓰입니다
특정 언어나 문법 규칙의 표현력이 어느 계산 모델에 대응하는지 설명할 때 기준으로 인용된다.
신경망 모델의 표현력 한계를 촘스키 위계상의 언어 클래스에 대응시켜 정량적으로 비교할 때 쓰이는 서술이다.
자연어 구문 분석에서 촘스키 위계를 자연어의 실제 복잡도를 논하는 근거로 인용하는 예다.
조금 더 깊게 보면
촘스키 위계의 각 단계는 대응하는 문법 형태(정규 문법, 문맥 자유 문법, 문맥 의존 문법, 무제한 문법)와 그것을 인식하는 오토마타(유한 오토마타, 푸시다운 오토마타, 선형 유계 오토마타, 튜링 기계)가 짝을 이루며, 논문에서 표현력을 논할 때는 흔히 이 문법-오토마타 대응 관계를 근거로 든다. 최근의 딥러닝 연구에서는 특정 신경망 구조가 위계상 어느 언어 클래스까지 학습·일반화할 수 있는지를 형식 언어 인식 실험(예: 괄호 짝맞추기, 특정 패턴의 반복 등 합성 과제)으로 검증하는 방식이 자주 쓰이며, 이런 실험은 모델의 이론적 표현력과 실제 학습 성능 사이의 간극을 드러내는 데 활용된다.
주의할 점
촘스키 위계의 각 단계는 포함 관계이지 동등한 것이 아니므로, '정규 언어이면서 문맥 자유가 아니다'라는 식의 혼동을 피해야 한다. 정규 언어는 문맥 자유 언어의 부분집합이다.