Chomsky  Hierarchy

 

......... 언어는 그 언어를 생성하는 최대로 제한되는 문법의 정도에 따라 구분한다.이는 촘스키 계층 (Chomsky hierachy) 이라고 하는, 제한된 문법의 형태 (따라서 각 문법에 의하여 생성되는 언어도 제한됨) 를 정의하는 한 가지 방법이다 .............

촘스키 계층 (Chomsky hierachy) 는 형식언어 (Formal Language) 를 생성하는 형식문법 (Formal Grammar) 들을 분류해 놓은 계층구조이다. 1956 년에 Noam Chomsky 가 처음 서술하였다. 그 계층구조는 다음과 같이 구분한다.

4 가지 유형의 문법, 그 문법이 생성하는 언어의 종류, 그 문법을 인식하는 오토마톤의 유형, 그 문법규칙들이 가지는 형태 .............. (Wikipedia : Chomsky hierarchy)

Grammar

Languages

Automaton

Production rules

Type-0

Recursively enumerable

튜링기계 (Turing Machine)

No restrictions (제한없음)

Type-1

Context-sensitive

Linear-bounded non-deterministic Turing machine

αAβ → αγβ

Type-2

Context-free

Non-deterministic pushdown automaton

A → γ

Type-3

Regular

Finite state automaton

AaB

ABa

Aa

......... 지금까지 여러 가지 언어군들을 살펴보았다. 순환적으로 열거가능한 언어 , 문맥-인식 언어 , 문맥-자유 언어 , 정규 언어 등이 여기에 해당한다. 이 언어군들 사이의 관계를 나타내는 한 가지 방법이 Chomsky 계층이다. 형식 언어 이론의 창시자인 Noam Chomsky 는 초기에 언어들을 네 가지 언어 형식들, type 0, type 1, type 2, type 3 으로 분류하였다. 이 원래의 용어가 지속되어 왔고, 사람들이 그것을 자주 참조하지만, 번호로 매겨진 형식은 실제로 우리가 연구하였던 언어군들에 대한 다른 이름들이다. type 0 언어는 무제한 문법에 의하여 생성되는 언어들이다. 즉, 순환적으로 열거가능한 언어이다. type 1 은 문맥-인식 언어들로 구성되고, type 2 는 문맥-자유 언어들로 구성되며, type 3 은 정규 언어들로 구성된다. 우리가 살펴본 바와 같이 type i 의 각 언어군은 type i - 1 언어군의 진부분 집합이다. 그림 3 의 다이어그램은 이들 사이의 관계를 명확히 보여준다. 그림 3 이 원래의 Chomsky 계층을 보여준다................. (Peter Linz 2001)

다음 표에서는 계산가능성 이론 (Computability Theory) (청색) 과 계산복잡도이론 (Computational Complexity Theory) (녹색) 에서 고려되는 문제들 (또는 언어, 문법들) 을 분류하는 일부를 보여준다. 만일 문제 X 가 Y 의 진부분집합 이라면 X 는 Y 의 아래에 위치하고 검은색 선으로 연결된다. 만일 X 가 부분집합이지만 같은 집합 (equal sets) 인지도 모를 때는 점선으로 연결된다.  

 

Decision Problem

 

 

 

SolidLine.png

 

SolidLine.png

 

 

Type 0 (Recursively enumerable)

 

Undecidable

SolidLine.png

 

 

 

 

 

Decidable

 

 

 

 

 

SolidLine.png

 

 

 

 

 

EXPSPACE

 

 

 

 

 

DottedLine.png

 

 

 

 

 

EXPTIME

 

 

 

 

 

DottedLine.png

 

 

 

 

 

PSPACE

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

Type 1 (Context-sensitive)

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

PSPACE-Complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

Co-NP

DottedLine.png

 

NP

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

SolidLine.png

SolidLine.png

DottedLine.png

BPP

 

BQP

 

NP-complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

P

SolidLine.png

SolidLine.png

DottedLine.png

 

DottedLine.png

SolidLine.png

NC

 

P-Complete

SolidLine.png

SolidLine.png

 

 

 

 

 

Type 2 (Context-free)

 

 

 

 

 

SolidLine.png

 

 

 

 

 

Type 3 (Regular)

 

 

 

 

 

term :

언어학 (Linguistics)   자연어 처리 (Natural Language Processing)   전산언어학 (Computational Linguistics)   인공언어 (Artificial Language)   형식언어 (Formal Language)   형식문법 (Formal Grammar)   AI 언어 (AI Language)   계산가능성 이론 (Computability Theory)    계산복잡도이론 (Computational Complexity Theory)   문맥자유 문법 (Context Free Grammar)   문맥인식 문법 (Context Sensitive Grammar)   촘스키 계층 (Chomsky Hierarchy)

paper :

문법과 언어의 종류 : 김재희

Chomsky 계층 : Peter Linz

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