일반적이고 문맥이없는 문법 중 하나가 더 강력합니다. 이유를 알려주세요.

Question

프로그래밍 언어의 원리를 살펴 보았습니다. 나는 정규적이고 문맥이없는 문법과 그 사용법의 개념을 안다. 그러나 아직도 나는 어느 것이 더 강력하고 왜 그런지를 결정할 수 없다. 도와주세요

미리 감사드립니다.

Answer 1

모든 일반 언어는 컨텍스트 프리이지만 일부 컨텍스트 프리 언어는 정규 언어가 아닙니다. 그러한 의미에서 문맥 자유 언어는 일반 언어보다 "강력합니다".

문맥 자유 언어가 아닌 비정규 언어의 한 예로, x 및 y 문자로 구성된 모든 문장의 언어를 고려하십시오. 펌핑 보조 정리 또는 Myhill-Nerode 정리를 사용하여이 언어가 비정규라는 것을 증명할 수 있습니다. 문법에 의해 생성 되었기 때문에 컨텍스트 프리입니다.

S → aSa | bSb | a | b | & ε;

직관적으로 정규 언어는 유한 메모리가있는 컴퓨터에서 해결할 수있는 예/아니오 질문에 해당합니다 (Myhill-Nerode 정리는이 직관을 형식화하는 한 가지 방법입니다). 즉 유한 메모리만으로는 해결할 수없는 예/아니오 문제는 일반 언어와 일치하지 않습니다. 상황이없는 언어는 이상한 중간계를 차지합니다. 유한 메모리와 무한대 스택을 사용하는 컴퓨터에서 해결할 수있는 문제에 해당합니다.

이 문제에 대해 자세히 알고 싶다면 공식 언어와 계산 능력에 대한 책을 읽어 보는 것이 좋습니다. 이러한 언어 클래스에 대해 놀랍도록 아름다운 결과가 많이 있으며이를 한 가지 대답으로 압축 할 수있는 방법은 없습니다.

희망이 도움이됩니다.