형식 언어 이론 및 오토마타

형식 언어와 이를 인식하는 추상 기계에 대한 이론으로, 언어 패턴의 복잡성과 이를 처리할 수 있는 알고리즘에 대한 어휘를 제공합니다.

Definition

형식 언어 이론은 문법에 의해 정의된 문자열 집합을 연구하며, 오토마타 이론은 해당 집합의 멤버십을 결정하는 추상 기계를 연구합니다.

Scope

촘스키 위계(정규, 문맥 자유, 문맥 의존, 재귀적으로 열거 가능한 언어)와 해당 문법, 그리고 이를 인식하는 오토마타(유한 상태 기계, 푸시다운 오토마타, 튜링 기계)를 다룹니다. 언어 처리에 관련된 폐쇄 및 결정 가능성 속성과 자연어가 위계에서 어디에 위치하는지에 대한 질문을 다룹니다. 펌핑 보조정리와 완전한 복잡성 증명은 주요 내용보다는 배경 지식으로 다루어집니다.

Core questions

• 각 촘스키 위계 수준에 해당하는 오토마타는 무엇입니까?
• 자연어는 위계에서 어디에 속하며, 왜 문맥 자유 능력을 초과한다고 주장됩니까?
• 언어 클래스가 연산에 대해 닫혀 있다는 것은 무엇을 의미하며, 이는 공학에 왜 중요합니까?

Key concepts

• 정규 언어
• 문맥 자유 문법
• 문맥 의존 문법
• 유한 상태 오토마타
• 푸시다운 오토마타
• 튜링 기계
• 폐쇄 속성
• 약한 문맥 의존성

Key theories

촘스키 위계

네 가지 중첩된 형식 언어 클래스로, 각각 제한된 문법 유형에 의해 생성되고 해당 오토마타에 의해 인식되며, 계산 능력에 따라 언어 구성을 순서화합니다.

문법-오토마타 대응 관계

각 문법 클래스는 기계 클래스와 증명 가능하게 동등합니다. 정규 문법은 유한 오토마타에, 문맥 자유 문법은 푸시다운 오토마타에 해당하며, 생성적 설명과 인식 알고리즘을 연결합니다.

History

촘스키의 1956년 논문은 유한 상태 모델이 자연어에 부적합하다는 주장의 일부로 위계를 도입했습니다. 이후 수십 년 동안 오토마타 대응 관계가 형식화되었고, 계산 언어학자들은 나중에 자연어가 기껏해야 '약한 문맥 의존성(mildly context-sensitive)' 능력을 요구한다는 것을 보여주어 문맥 자유 문법을 넘어서는 문법 형식론을 촉진했습니다.

Debates

자연어는 문맥 자유 언어인가?

스위스 독일어와 같은 언어의 교차 종속성(cross-serial dependencies)은 자연어가 문맥 자유 능력을 초과한다는 주장의 근거로 사용되었으며, 이는 적절한 표현력 수준으로서 약한 문맥 의존성이라는 개념으로 이어졌습니다.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

정규 언어와 문맥 자유 언어의 차이점은 무엇입니까?

정규 언어는 유한 상태 오토마타에 의해 유한한 메모리로 인식될 수 있습니다. 문맥 자유 언어는 균형 잡힌 괄호나 내장된 절과 같은 중첩된 구조를 추적하기 위해 스택(푸시다운 오토마타)을 필요로 할 수 있습니다.