언어가 비 결정적 튜링 기계의 문맥에 민감하다는 것을 어떻게 보여줄 수 있습니까?비 결정적 튜링 기계가있는 상황에 맞는 언어
LBA (Linear Bound Automated Automaton)에서 허용하는 언어는 상황에 영향을받지 않는 언어라는 것을 알고 있습니다. 그리고 LBA는 비 결정적 튜링 기계입니다.
어떤 생각이라도 내가이 모든 것을 어떻게 연관시킬 수 있으며 문맥에 민감한 언어임을 보여줄 수 있습니까?
, 나는 귀하의 질문에 대한 신속한 답변을 제공 :
언어는 컨텍스트 할 수 있다면 (그리고 경우에만) 민감 L을 정의하는 선형 공간을 사용하여 비 결정적 튜링 기계를 제공하십시오.
임의의 정수 n에 대해 L = {a^nb^na^n}이라고합시다. a^n은 기호 a의 n 개의 연결을 의미합니다. 이것은 일반적인 상황에 맞는 언어입니다. CSG를주는 대신 L이 문맥에 민감하다는 것을 보여주기 위해 LBA를 줄 수 있습니다 :
튜링 기계 M은 '비 결정적 성향 덕분에요'라고 추측합니다. 즉, '비 결정적 검색의 모든 지점 트리가 다른 n을 시도한 다음] 입력이^nb^na^n과 일치하는지 확인합니다. n을 저장하기 위해 log n 셀이 필요합니다. 일치가 다른 log n 셀을 필요로 할 수도 있습니다. n + 2log n < 2n과 같이이 기계는 선형 공간 만 필요하므로 LBA이므로 L은 상황에 따라 다릅니다.
NSPACE (n) = CSL이라는 증거가 있습니까? 나는이 결과에 대해 들어 본 적이 없지만 정말 멋지다! – templatetypedef
예, 1969 년에 입증되었습니다. 나는 증거가있는 공개 논문을 찾을 수 없다. ComplexityZoo (Scott Aaronson의 복잡성 문제 질문에 대한 아주 훌륭한 참고서)는 http://www.sciencedirect.com/science/article/pii/S0022000069800322를 참고로하고있다. Google이 공개적으로 사용할 수있는 다른 증거를 뱉어 냈을 수도 있습니다. –
이것은 정확한 대답은 아니지만 상황에 맞는 언어가 선형 경계 오토마타 (테이프에 O (n) 공간이있는 TM)에 의해 정확하게 수용되므로 문맥에 민감한 언어는 정확하게 DSPACE (n)에서. 또한 NTIME(n) = DSPACE(n)을 알고 있습니다. 즉, 일부 언어 L의 멤버십을 결정하는 선형 시간 NTM을 찾을 수 있으면 해당 언어가 상황에 맞는 것임을 의미합니다. 그러나 여전히 선형 시간 NTM이없는 상황에 맞는 언어가있을 수 있습니다 (이 문제에 대한 명확한 대답이 있는지 여부 또는 열린 문제인지 여부는 알 수 없음). 따라서 정확한 특성이 아닙니다. .
희망이 도움이됩니다. templatetypedef의 대답은 (내가 코멘트에서 두 번째로 지적 할 것이다) 약간의 결함이 있기 때문에
언급 한 바와 같이,이 대답은 약간의 오류가 있습니다 : 한편으로 우리는 DSPACE (n)가 NTIME (n)의 부분 집합인지 여부를 알지 못합니다. 다른 방법은 분명합니다. 반면 CSL은 정확히 DSPACE (n)가 아닌 NSPACE (n)의 언어입니다. 열린 문제이지만 DSPACE (n)가 NSPACE (n)의 적절한 하위 집합이라고 믿었습니다. –
CSTheory.stackexchange는 연구 수준의 질문을 요구합니다. 그러나 math.stackexchange는 이러한 질문에 매우 적합합니다. 또한, 그들은 답의 알맞은 형식화를 위해 LaTeX를 지원합니다. –