촘스키 위계

촘스키 위계는 형식 언어를 네 가지 중첩된 클래스로 분류하며, 각 클래스는 문법 규칙에 대한 제약으로 정의되고 특정 종류의 추상 기계와 일치합니다.

Definition

촘스키 위계는 생성 규칙에 대한 점진적으로 더 강력한 제약을 통해 형식 문법을 분류한 것으로, 정규, 문맥 자유, 문맥 의존, 재귀적으로 열거 가능한 언어 클래스를 엄격한 포함 관계의 사슬로 산출합니다.

Scope

이 주제는 무제한(unrestricted), 문맥 의존(context-sensitive), 문맥 자유(context-free), 정규(regular)의 네 가지 문법 유형과 이들의 엄격한 포함 관계, 그리고 각 수준에 해당하는 오토마타 모델(튜링 기계, 선형 제한 오토마타, 푸시다운 오토마타, 유한 오토마타)을 다루며, 각 수준을 구분하는 폐쇄(closure) 및 결정 가능성(decidability) 속성도 포함합니다.

Core questions

• 문법 규칙에 대한 제약이 기억 및 컴퓨팅 능력의 한계로 어떻게 전환되는가?
• 위계의 각 수준이 다음 수준에 엄격하게 포함되는 이유는 무엇인가?
• 각 문법 유형에 해당하는 오토마타 모델은 무엇인가?
• 위계가 올라갈수록 결정 가능성 및 폐쇄 속성은 어떻게 변화하는가?

Key theories

문법-기계 대응 관계

각 문법 클래스는 특정 기계 모델에 의해 인식됩니다. 정규 문법은 유한 오토마타, 문맥 자유 문법은 푸시다운 오토마타, 문맥 의존 문법은 선형 제한 오토마타, 무제한 문법은 튜링 기계에 의해 인식되어, 계산의 생성적 설명과 작동적 설명을 연결합니다.

언어 클래스의 엄격한 포함 관계

각 수준은 구체적인 분리 언어에 의해 증명되듯이 그 아래 수준을 적절히 포함하므로, 이 위계는 동등한 설명들의 집합이라기보다는 표현력 증가의 진정한 사다리입니다.

Clinical relevance

이 위계는 형식 언어 이론의 조직화된 지도로서, 프로그래밍 언어, 쿼리 언어, 프로토콜 사양의 설계자들에게 주어진 패턴 클래스가 요구하는 기계 장치의 양을 알려주며, 결정 가능한 것과 인식 가능한 것 사이의 경계를 설정합니다.

History

촘스키는 1950년대 후반 자연어 구문의 형식 모델을 탐색하면서 이 위계를 제안했으며, 1960년대 오토마타 이론이 발전하면서 기계 대응 관계가 확립되었습니다. 선형 제한 오토마타는 Myhill에 의해 도입되었고 문맥 의존 수준은 Kuroda에 의해 명확해졌습니다.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

촘스키 위계의 네 가지 수준은 무엇입니까?

가장 약한 것부터 가장 강력한 것 순으로 정규 언어(유형 3), 문맥 자유 언어(유형 2), 문맥 의존 언어(유형 1), 재귀적으로 열거 가능한 언어(유형 0)입니다. 각 수준은 문법 규칙에 대한 제약을 완화하고 더 많은 메모리를 가진 기계에 해당합니다.

자연어는 촘스키 위계에 의해 포착됩니까?

이 위계는 원래 언어학에 의해 동기 부여되었지만, 대부분의 언어학자들은 자연어가 문맥 자유가 아니며 종종 '약간 문맥 의존적(mildly context-sensitive)'이라고 불리는 수준에 있다고 결론 내립니다. 인간 언어가 느슨하게만 들어맞더라도 이 위계는 컴퓨터 과학에서 여전히 기초적입니다.