문맥 자유 언어 및 푸시다운 오토마타

문맥 자유 문법은 중첩되고 재귀적인 구조를 가진 언어를 생성하며, 푸시다운 오토마타는 무한 스택으로 유한 제어 장치를 보강하여 정확히 이러한 언어를 인식합니다.

Definition

문맥 자유 언어는 문맥과 독립적으로 단일 비단말 기호를 재작성하는 규칙을 가진 문법에 의해 생성되며, 무한 깊이의 후입선출 메모리를 제공하는 스택을 갖춘 유한 오토마타인 푸시다운 오토마타에 의해 인식됩니다.

Scope

이 주제는 문맥 자유 문법 및 유도, 파스 트리 및 모호성, 문맥 자유 문법과 푸시다운 오토마타의 동등성, 촘스키 정규형과 같은 정규형, 문맥 자유 언어에 대한 펌핑 보조정리, 그리고 이 클래스를 정규 언어와 구별하는 폐쇄 및 결정 속성을 다룹니다.

Core questions

• 어떤 종류의 중첩되거나 재귀적인 패턴이 유한 메모리 대신 스택을 필요로 하는가?
• 문맥 자유 문법과 푸시다운 오토마타가 능력 면에서 동등한 이유는 무엇인가?
• 문법이 모호한 경우는 언제이며, 파싱에 있어 모호성이 중요한 이유는 무엇인가?
• 문맥 자유 언어에 대한 어떤 결정 문제가 해결 가능하며, 어떤 문제는 해결 불가능한가?

Key theories

문법-오토마타 동등성

언어는 어떤 푸시다운 오토마타에 의해 수용될 경우에만 문맥 자유 언어이며, 따라서 생성 문법 관점과 스택 기계 관점은 동일한 언어 클래스를 설명합니다.

촘스키 정규형

모든 문맥 자유 문법은 각 규칙이 두 개의 비단말 기호 또는 단일 단말 기호를 생성하도록 재작성될 수 있으며, 이는 파싱 알고리즘과 클래스에 대한 귀납적 증명의 기반이 되는 정규형입니다.

문맥 자유 언어에 대한 펌핑 보조정리

문맥 자유 언어의 모든 충분히 긴 문자열은 두 부분이 함께 펌핑되도록 분할될 수 있으며, 이 속성은 스택 메모리 이상을 요구하는 언어에서는 실패하므로 해당 언어가 문맥 자유 언어가 아님을 증명합니다.

Clinical relevance

문맥 자유 문법은 거의 모든 프로그래밍 언어와 많은 데이터 형식의 구문을 지정하며, 푸시다운 방식의 파싱 알고리즘은 이러한 문법을 컴파일러 및 인터프리터의 핵심인 구문 분석기로 변환하여 이 주제를 프로그래밍 언어 처리의 이론적 기반으로 만듭니다.

History

촘스키는 1950년대 후반 자신의 계층 구조의 일부로 문맥 자유 문법을 도입했으며, 백커스와 나우어는 ALGOL 프로그래밍 언어의 구문을 정의하기 위해 독립적으로 이를 사용했습니다. 푸시다운 오토마타와의 동등성 및 클래스의 구조 이론은 1960년대에 연구되었습니다.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

프로그래밍 언어를 파싱하는 데 스택이 필요한 이유는 무엇인가?

프로그램에는 괄호, 블록, 함수 호출과 같이 중첩된 구성 요소가 포함되어 있으며, 이들의 일치 깊이는 무한합니다. 스택은 각 미완성 구성 요소를 기록하고 닫힐 때 팝(pop)하는데, 이는 푸시다운 오토마타가 제공하고 유한 오토마타에는 없는 정확한 메모리 관리 방식입니다.

문법이 모호하다는 것은 무엇을 의미하는가?

문법은 어떤 문자열이 둘 이상의 파스 트리를 가질 때 모호하다고 합니다. 이는 문자열이 진정으로 다른 구조로 유도될 수 있음을 의미합니다. 모호성은 코드의 의미를 불분명하게 만들기 때문에 프로그래밍 언어에서는 바람직하지 않으므로, 언어 설계자들은 모호하지 않은 문법을 찾거나 모호성 해소 규칙을 추가합니다.