저는 오토 마타 이론에 관한 수업을 진행하고 있습니다. 그리고 지금 우리는 펌핑 보조 정리를 배우고 있습니다. 우리에게 "L이나 그 보완도 무한한 정규 하위 집합을 갖지 않도록 언어 L을 설계하라"고 요구하는 운동 질문이 있습니다. 그러나 나는 그 질문을 이해하지 못한다. 무한한 정규 하위 집합이란 무엇입니까? 이 요구 사항을 충족시킬 수있는 언어를 어떻게 찾을 수 있습니까?L도 보완도 무한한 정규 하위 집합을 갖지 않도록 언어 L을 설계 하시겠습니까?
누구나이 질문에 대해 밝힐 수 있습니까?
감사합니다.
보다 정확하게는 L을 찾아서 L의 하위 집합이 무한 정규 언어이고 무한 정규 언어 인 L의 하위 집합이 없도록해야합니다.
여기에 잘못된 예가 나와 있습니다. L = a^n과 a^n b^n의 합집합입니다. a^n은 (는) 정규 언어이며 L의 하위 집합이므로 답변에 적합하지 않습니다.
요구 사항을 충족하는 L을 찾으려면 이러한 종류의 질문이 퍼즐과 비슷하다는 것을 발견했습니다. 몇 가지 일을 시도하고, 그들이 작동하는지 아닌지를 확인한 다음 문제를 해결하지 못한 이유에 대해 생각해보십시오. 궁극적으로 당신은 상황을 생각하고 해결책을 내놓을 것입니다.
질문의 자세한 버전을 제공해 주셔서 감사합니다. 이제 질문이 무엇인지 묻습니다. 나는 당신의 제안을 따르고 해결책을 생각해 낼 것입니다. –
음, 무한한 정규 하위 집합은 무한하고 규칙적인 하위 집합입니다. 좋아, 그다지 도움이되지 않을거야.
"하위 집합"은 매우 명확합니다.
"정규 하위 집합"은 결정 론적 유한 상태 기계에서 허용되는 개념입니다 (실제로이 조건은 몇 가지 다른 조건과 동일하다는 언어 이론에 놀라운 이론이 있습니다).
"무한한 세트"는 한정되지 않은 세트 또는 동등하게 많은 요소가있는 세트입니다.
그럼 언어가 L은 무한한 정규 하위 집합이있는 경우 특별하다고 가정 해 보겠습니다.
L과 L의 양쪽 모두가 특별하지 않은 언어 인 L을 찾는 것이 좋습니다.
이 문제가 발생하면 먼저 해당 정의를 머리에 감싸 야합니다. 메모와 텍스트에서 몇 가지 예를 들어 보겠습니다. 그들이 규칙 적인지 파악하십시오. 그렇지 않은 언어를 발견하면 규칙적인 언어가 아닌 것에 대해 생각해보고 무한한 하위 집합이 모두 규칙적이지 않은 속성을 가진 언어를 디자인하는지 확인하십시오. 그런 다음 보완을 보면 어떤 일이 일어나는 지보십시오.
직감을 구축해야하며 그렇게하려면 손을 더럽힐 수있는 유일한 방법입니다.
몇 가지 정의를 설명해 주셔서 감사합니다! 나는이 개념을 이해하려고 노력할 것입니다. 그리고이 질문에 대한 약간의 강의를 가지기를 바랍니다.) –
시도해보십시오. http://cstheory.stackexchange.com/ –