언어 L은 정규 언어에 대한 펌핑 보조 정리와 문맥 자유 언어에 대한 펌핑 보조 정리를 만족시킵니다. L에 대한 다음 진술 중 무엇이 사실입니까?정규 언어에 대한 펌핑 보조 정리와 문맥 자유 언어에 대한 펌핑 보조 정리를 만족하는 언어 L에 관해 말할 수있는 것은 무엇입니까?
A. L은 반드시 정규 언어입니다.
B. L은 반드시 CFL이지만 Regular는 아닙니다.
C.L은 반드시 비정규이다.
D. 없음
나는 의심 스럽습니다. L이 정규 언어에 대한 펌핑 보조 정리를 만족하면 반드시 정규화 된 것은 아닙니다. 컨텍스트가없는 것과 동일합니다. 따라서 정규 또는 비정규가 될 수 있습니다. CFL 또는 비 CFL. 주어진 대답은 B입니다.하지만 제 의견으로는 D.이어야합니다. 내가 누락 된 부분을 지적 해 줄 수 있습니까?
응답 B가 맞지 않습니다. Σ *을 사용해보십시오.이 언어는 절대적으로 규칙적이며 문맥이 없습니다. 또한 두 펌핑 보조 정리의 조건을 전달합니다. 따라서 언어가 컨텍스트 프리이지만 규칙적이지는 않습니다.
모두 펌핑 보조 정리는 언어가 일반 또는 상황이 없어야 할 필요한 조건이 아니라 그 언어가 일반 또는 상황이 없어야 할 충분한 조건을 제공합니다. 따라서 언어가 두 펌핑 보조 정리를 모두 통과하면 일 수도 있고 일 수도 있고 일 수도 있고 일 수도 있습니다. 그러나 이것이 반드시 필요한 것은 아닙니다.
저는 D가 올바른 선택임을 확신합니다.
희망이 도움이됩니다.
그게 범인의 보조 정리가하는 것이 아닙니다. 그것들은 일반/CFL 언어의 속성으로 기술 할 수 있습니다.이 경우 언어는 CF와 일반 (그 시나리오의 전제이기 때문에)이므로 정규 언어이거나 언어가 CF/정규가 아님을 암시하는 속성으로 명시 될 수 있습니다 ,이 경우 언어는 CF (비정규 인 것을 포함)가 아닙니다. 그러나이 질문은 펌핑 보조 정리 (pumping lemma)의 변종 중 어느 것이 말하는지를 말하지 않습니다. – Fizz
@RespawnedFluff 내가 언급 한 펌핑 보조 정리의 변형을 본 적이 없습니다 (언어에 속성이있는 경우 CFL이 아닙니다). 이것에 대한 참조를 제공 할 수 있습니까?나는 그들이 어떻게 일하는 지 궁금하다. – templatetypedef
"p implies q"형식의 수학적 문장은 "non-q implies non-p"로 다시 표시 할 수 있습니다. 그리고 펌핑 보조 정리와 정확히 같은 일이 생깁니다 ... 펌핑 보조 정리는 종종 후자 형태의 증명에서 사용됩니다 (R/CF 펌핑 속성을 갖지 않으면 언어가 R/CF가 아님을 의미 함). 그러나 간단한 설문 조사를 한 후에는 원문에 어마 어마한 문장 *으로 첫 번째 형식 (R/CF 언어는 R/CF 펌핑 속성을 가짐)이 우세하다는 것을 알게되었습니다. [다음 글 코멘트 길이 제한으로 계속] – Fizz
음 ...이 사이트는 사람들이 무료로 숙제를 할 수있는 방법이 아닙니다. –
이것은 숙제가 아닙니다. 나는이 질문에 의심의 여지가있다. 언어가 정규 언어에 대한 보조 정리를 만족시키는 경우 정규 언어 일 필요는 없습니다. –
"응답은 B이지만 내 의견으로는 B 여야합니다. 누군가 내가 누락 된 부분을 지적 할 수 있습니까?" - 주어진 답이 B이고, B가되어야한다고 생각한다면 실종 될 것 같습니다. 그런 다음 빠진 것은없는 것 같습니다. – Prateek