촘스키 위계

촘스키 위계(Chomsky hierarchy, 촘스키 계층)는 형식 문법을 생성 규칙에 거는 제한의 강도에 따라 0형부터 3형까지 네 단계로 나누고, 각 단계가 만드는 언어와 그 언어를 인식하는 기계를 짝지은 분류 체계이다.

개요

1956년 언어학자 노엄 촘스키가 자연어의 구조를 형식적으로 기술하려고 제안했다. 문법은 생성 규칙(α → β) 의 모음이고, 규칙의 왼쪽과 오른쪽에 무엇을 쓸 수 있는지를 좁혀 갈수록 표현할 수 있는 언어의 범위도 좁아진다. 0형이 가장 넓고 3형이 가장 좁으며, 아래 단계의 언어는 모두 위 단계의 언어에 포함된다.

컴파일러에서는 3형(정규 문법)으로 토큰의 구조를 기술해 어휘 분석에 쓰고, 2형(문맥 자유 문법)으로 문장의 구조를 기술해 구문 분석에 쓴다.

네 가지 문법

유형	문법	생성 규칙의 제한	생성하는 언어	인식하는 기계
0형(Type 0)	무제한 문법(unrestricted grammar)	제한이 없다. α → β (α 에 비단말 기호가 하나 이상)	귀납적 열거 가능 언어	튜링 기계
1형(Type 1)	문맥 의존 문법(context-sensitive grammar)	α\| ≤ \|β\|	문맥 의존 언어	선형 제한 오토마타(선형 구속 오토마타, LBA)
2형(Type 2)	문맥 자유 문법(context-free grammar)	왼쪽이 비단말 기호 하나다. A → β	문맥 자유 언어	푸시다운 오토마타(스택을 가진 오토마타)
3형(Type 3)	정규 문법(regular grammar)	오른쪽이 단말 기호 하나에 비단말 기호를 많아야 하나 붙인 꼴이다. A → aB 또는 A → a (또는 Ba)	정규 언어	유한 오토마타

포함 관계 : 정규 언어 ⊂ 문맥 자유 언어 ⊂ 문맥 의존 언어 ⊂ 귀납적 열거 가능 언어
위로 갈수록 인식하는 기계에 붙는 기억 장치가 커진다. 유한 오토마타는 상태만, 푸시다운 오토마타는 스택 하나, 선형 제한 오토마타는 입력 길이만큼의 테이프, 튜링 기계는 무한한 테이프를 쓴다
0형의 인식기는 튜링 기계다. 그냥 '오토마타'라고 하면 어느 단계인지 정해지지 않으므로 0형과 짝지을 수 없다

정규 문법(3형)

3형 문법은 문맥 자유 문법의 생성 규칙에 제한을 더 둔 문법이다. 비단말 기호가 오른쪽 끝에 오느냐 왼쪽 끝에 오느냐에 따라 두 가지가 있다.

종류	규칙의 꼴	예
우선형(right-linear) 문법	A → aB, A → a	S → aS, S → b
좌선형(left-linear) 문법	A → Ba, A → a	S → Sa, S → b

한 문법 안에서는 우선형이나 좌선형 한쪽만 써야 한다. 두 꼴을 섞은 문법은 정규 언어가 아닌 언어(예: aⁿbⁿ)도 만들 수 있어 정규 문법이 아니다. 그래서 정규 문법의 종류는 우선형과 좌선형 두 가지이고 '혼합형'은 없다
정규 문법이 생성하는 언어를 정규 언어라 한다. 정규 언어는 유한 오토마타가 인식하는 언어이자 정규 표현식으로 나타낼 수 있는 언어다
식별자·숫자·키워드 같은 토큰의 구조를 표현하는 데 쓴다

시험에서 헷갈리는 것

문법과 인식기의 짝 : 0형 - 튜링 기계, 1형 - 선형 제한 오토마타, 2형 - 푸시다운 오토마타, 3형 - 유한 오토마타. 순서를 바꾸거나 0형에 그냥 '오토마타'를 붙인 보기는 틀렸다
"유한 오토마타가 문맥 자유 언어를 인식한다"는 틀렸다. 괄호의 짝을 맞추려면 스택이 있는 푸시다운 오토마타가 필요하다
프로그래밍 언어의 문법은 대부분 2형(문맥 자유 문법)으로 정의하고 BNF 로 적는다

같이 보기