Chomsky의 계층 구조에서 재귀 언어 집합은 정의되지 않습니다. 재귀 언어는 재귀 적으로 열거 가능한 언어의 하위 집합이고 모든 재귀 언어는 결정할 수 있다는 것을 알고 있습니다.재귀 언어와 상황에 맞는 언어
제가 궁금한 점은 재귀 언어가 상황에 맞는 언어와 어떻게 비교되는지입니다. 상황에 맞는 언어가 반복적 인 언어의 엄격한 하위 집합이라고 가정 할 수 있습니다. 따라서 모든 상황에 민감한 언어는 결정할 수 있습니까?
모든 상황에 맞는 언어가 모든 재귀 적 언어 집합에있는 경우에만 질문하는 경우 형식 자동 형식을 통해 고전적인 방법으로이를 증명하려고 시도해야합니다. 공식 자동화가 상황에 민감한 언어의 생성을 시뮬 레이팅 할 수 있는지 그리고 재귀 언어를 생성하는 데 사용되는 것이 무엇인지 스스로에게 물어보십시오. 그런 다음 다른 하나를 사용하여 시뮬레이션하십시오. 교과서에서 올바른 오토마타를 찾으면 원하는 것을 증명할 수 있습니다.
일련의 상황에 맞는 언어는 재귀 적 언어의 적절한 하위 집합입니다. 당신은 이것을 짐작할 필요가 없습니다. Peter Linz의 책을 참고하십시오.
재귀 언어를 인식하려면 Decider이라는 종류의 자동화 장치가 필요합니다. 제한된 제어 흐름으로 트릭 된 Turing Machine입니다. 즉, 항상 중단되도록합니다.
상황에 맞는 언어에 대해서는 실제로는 재귀 적 언어의 적절한 하위 집합입니다. 문맥에 민감한 언어를 인식하는 최소한의 자동화 기능을 제공하는 것은 간단합니다. Linear bounded automaton은 결정자보다 강력하지 않습니다. 나는 또한 문법 제약 규칙에 근거하여 설명하는 것이 가능할 것이라고 생각한다.
Papadimitriou의 저서 (3.4.2 (e))에 따르면 상황 별 문법은 재귀 언어의 적절한 하위 집합 인 NSPACE (n)과 동일합니다. 그렇습니다. 당신의 가정은 정확합니다.
질문에 대한 대답이 아닙니다. –