0
여부 Decidable 그 것이다 :주어진 문맥 자유 언어가 정규 여부
주어진 문법은 문맥 무료?
주어진 재귀 언어는 컨텍스트 프리입니까?
주어진 컨텍스트 무료 언어가 규칙적입니까? 주어진 문법이 Greibach의 정리를 사용하여
없는 상황 인 경우
A
답변
2
주어진 문법이 우리에게 언어를 줄 수 있고, 언어를 사용하고 보조 정리를 펌핑, 우리가 쉽게 결정할 수 있습니다, 우리는 결정 불가능임을 표시 할 수 있습니다 문맥 자유 언어가 규제자인지 아닌지를 묻는 질문에 대답 해주십시오.
+0
고마워요. 문맥이없는 재귀 적 언어의 결정 가능성/결정 불가능 성을 증명하는 정리가 있습니까? – user1892450
+0
@ user1892450 : 사실, 나는 아직 그처럼 찾아 오지 못했지만 ... 당신의 독서 자료의 NP-hard 및 NP-Complete 문제 섹션을 통해 어떤 것이 있는지 검색 할 수 있습니다 .... –
답변 : 확실하지 않은 이유는 무엇입니까? – rook
이것은 정확하게 숙제가 아닙니다. 나는 decidability에 대해 읽고 있었고 이러한 질문은 내 마음에 왔습니다. – user1892450
예 ...하지만 숙제 섹션에있는 사람들은 도움을 줄 수 있습니다. 이 질문은 아마도 cstheory.stackexchange.com에 더 적합 할지라도. – rook