촘스키 위계

위키백과 ― 우리 모두의 백과사전.

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

목차

[편집] 언어

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

  • 알파벳 T는 기호들의 유한집합이다.
  • 언어 LT *부분집합이다.

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

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

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

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

[편집] 문법

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

G = (VN,VT,P,S)

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

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

  • VN의 윈소인 비말단 기호는 A,B,C 등의 영문자 대문자로 표기한다.
  • VT의 원소인 말단 기호는 a,b,c 등의 영문자 소문자로 표기한다.
  • V (=V_N \cap V_T)의 원소는 α,β,γ 등 그리스문자로 표기한다. 즉, 비말단과 말단을 구별하지 않을 때이다.
  • 빈 문자열은 ε로 표기한다.

[편집] 위계

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


[편집] 제0유형 문법

제약없는 문법(UG, unrestricted grammar). 생성규칙(production rule)에 제약을 두지 않는다. 단, \alpha \rightarrow \beta에서 \alpha \neq \epsilon

[편집] 제1유형 문법

문맥 의존 문법(CSG, context-sensitive grammar). 모든 생성 규칙은 \alpha \rightarrow \beta에서 |\alpha| \leq |\beta|이다.

[편집] 제2유형 문법

문맥 자유 문법(CFG, context-free grammar). 모든 생성 규칙은 A \rightarrow \alpha형태를 갖는다. (A는 하나의 비말단(nonterminal)이고, αV * 에 속하는 문자열이다.

[편집] 제3유형 문법

정규 문법(RG, regular grammar). 모든 생성규칙은 다음 2가지 중 하나로 표현된다:

  • (1) A \rightarrow tB 또는 A \rightarrow t, 여기서 t \in {V_T}^*이고, A, B \in V_N이다.
  • (2) A \rightarrow Bt 또는 A \rightarrow t, 여기서 t \in {V_T}^*이고, A, B \in V_N이다.

[편집] 형식문법의 촘스키 위계

유형 문법 언어 오토마타 생성규칙 언어의 예
제 0유형 제약없는 문법 귀납적 가산 언어 튜링 기계 제약 없음 -
제 1유형 문맥의존문법 문맥의존언어 선형 구속형 비결정성 튜링 기계 αAβ → αγβ anbncn
제 2유형 문맥자유문법 문맥자유언어 비결정성 푸시다운 오토마타 A → γ anbn
제 3유형 정규문법 정규언어 유한 상태 기계 AaB
Aa
an

[편집] 참고문헌

  • 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
오토마타 이론: 형식 언어 및 형식 문법
촘스키 위계 형식 문법 형식 언어 최소한의 자동장치
Type-0 (무제약) 순환 열거 언어 튜링 기계
(무제약) 순환 언어 판정자
Type-1 문맥 의존 문법 문맥 의존 언어 선형유한 오토마타
Type-2 문맥 무관 문법 문맥 무관 언어 내리누름 오토마타
Type-3 정규 문법 정규 언어 유한 오토마타
각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다.