تست ۱۲۱ علوم کامپیوتر۸۸
برای حل این سوال باید صورت سوال رو خوب متوجه شد که چی میگه:
c کلاس تمام زبانهای مستقل ازمتن هست و c’ یه سری از زبانهاست که متمم اون مستقل ازمتن میشه. سوال A رو به صورت A=c n c’ (n=اشترک) کرده. خوب c که مستقل ازمتن هست اما c’ چی؟ پس اگه می خوایم A تهی نشه باید c’ زبانهایی باشه که اشتراک متمم اون با c یعنی مستقل از متن‌ها تهی نشه.
زبانهای کاندید برای c’: منظمها و مستقل از متن معین ها. می دانیم که زبانهای مستقل ازمتن تحت متمم بسته نیست اما مستقل از متن معین تحت متمم بسته است.
گزینه های یک و دو معادل هم هستند و یک زبان منظم رو توصیف می کنند پس قاعدتا نمی تواند جواب باشد که البته با مثال هم میشه ثابت کرد که بازه فراتر از منظمها هست.
گزینه ۳ میگه برای هر زبان مستفل از متن L اما می دونیم که زبانهای مستقل از متن تحت متمم بسته نیستند.
جواب گزینه ۴ هست که توصیفی از زبانهای مستقل معین هست که تحت متمم بسته هستند و اشتراک با زبانهای مستقل ازمتن دارند.