촘스키 위계

촘스키 위계(Chomsky hierarchy)는 형식 언어를 생성하는 형식 문법의 클래스 사이의 위계를 말한다. 노엄 촘스키가 1956년에 제시하였다.

언어 
언어는 형식적으로 문장들의 집합으로 정의될 수 있고, 문장은 형식적으로 기호들의 연쇄로 정의될 수 있다.

 알파벳 는 기호들의 유한 집합이다.
 언어 은 의 부분집합이다.

예를 들어,  {ㄱ, ㄴ, ㄷ, ㄹ, ..., ㅎ, ㅏ, ㅑ, ㅓ, ㅕ, ..., ㅡ, ㅣ}라고 했을 때 다음과 같은 언어들이 있을 수 있다.

 {ㄱㅏ, ㄴㅏ, ㄷㅏ, ㄹㅏ, ..., ㅎㅏ}

 {ㄱㅏㄷㅏ, ㅅㅏㄷㅏ, ㅈㅏㄷㅏ, ㅊㅏㄷㅏ, ㅌㅏㄷㅏ, ㅍㅏㄷㅏ, ㅎㅏㄷㅏ}

 {ㄱㄱㅏㄷㅏ, ㄷㄷㅏㄷㅏ, ㅅㅅㅏㄷㅏ, ㅈㅈㅏㄷㅏ}

문법 

문법은 형식적으로 기호들의 집합에 그 기호들로부터 문장을 만드는 규칙이 부여된 것으로 정의될 수 있다.

  : 비말단 기호의 유한 집합
  : 말단 기호의 유한 집합
  : 생성규칙의 유한 집합
  : 에 속하는 기호로 시작 기호 또는 문장 기호

형식문법을 기술하는 데 있어서 몇가지 기호 사용의 관례가 있다.

 의 원소인 비말단 기호는  등의 영문자 대문자로 표기한다.
 의 원소인 말단 기호는  등의 영문자 소문자로 표기한다.
 의 원소는  등 그리스문자로 표기한다. 즉, 비말단과 말단을 구별하지 않을 때이다.
 빈 문자열은 로 표기한다.

위계 

이렇게 정의된 형식문법은 생성규칙에 어떠한 제약이 있는가에 따라서 다음과 같이 나눌 수 있다.

제0유형 문법 
무제약 문법(UG, unrestricted grammar)은 생성규칙(production rule)에 아무런 제약을 두지 않으나, 좌변이 공집합이 되는 경우만은 없다(즉 에서 ). 이들은 모든 종류의 형식 문법을 포함한다. 이는 튜링 기계가 인식가능한 모든 언어를 생성하는데, 이를 재귀적 열거 가능 언어(recursively enumerable set)라 한다.

제1유형 문법 
문맥 의존 문법(CSG, context-sensitive grammar)은 문맥 의존 언어를 생성한다. 생성 규칙은 이며, 이들은 항상 에서 이다. 선형 구속 오토마타로 인식할 수 있다.

제2유형 문법 
문맥 자유 문법(CFG, context-free grammar)은 문맥 자유 언어를 생성한다. 모든 생성 규칙은 형태를 갖는다. (는 하나의 비말단(nonterminal)이고, 는 에 속하는 문자열.) 푸시다운 오토마타로 인식할 수 있다.

제3유형 문법 
정규 문법(RG, regular grammar)은 오른쪽 정규 문법과 왼쪽 정규 문법의 총칭이다. 다음은 각 생성규칙:
 (오른쪽 정규 문법)  또는 , 여기서 이고, 이다.
 (왼쪽 정규 문법)  또는 , 여기서 이고, 이다.

이로부터 모든 정규 언어를 기술할 수 있으며, 정규 표현식과 등가이기에 유한 상태 기계가 인식할 수 있다.

형식문법의 촘스키 위계

참고 문헌 
 Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
 Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112

전산언어학
노엄 촘스키
1956년 컴퓨팅