۵۶: چرا گزینه اول منظمه؟ فقط یه a یا b باید آخرش باشه! گزینه دوم چرا منظمه؟ مگه نباید تعداد a و bها با هم برابر باشند و در اطرافشون یه تعداد a,b باشه؟
۵۷: مگه لم تزریق دال بر نامنظم بودن نیست؟ به عبارتی وقتی خواستیم ثابت کنیم زبانی نامنظمه باید از لم تزریق استفاده کنیم. حالا چرا گزینه دوم صحیح نیست؟ گزینه سوم واسه اثبات عدم مستقل از متنه که!
۵۸: منظور سوال رو متوجه نمی شم
فکر کنم توی این بحث هنوز مشکل دارین. یکی از حالات در سوال ۵۶ برای این دو گزینه n=0 هست. با این حالت شما میتونین تمام حالات ممکن برای بقیه مقادیر n رو بسازید. یعنی زبان گزینه اول سیکما استار و زبان گزینه دوم b*a* میشه.
برای سوال ۵۷ میگه به ازای همه iها رشتمون توی زبانه. نه اینکه به ازای یه ه رشتمون توی زبان نیست. تعریف دوم لم تزریقه و گزینه ۲ اینو نمیگه. برای گزینه ۳ هم به این دلیل درسته که اگه یه زبان مستقل از متن نباشه مسلماً منظم هم نیست. شرط کافیه.
سوال ۵۸ هم یعنی زبانی که به یک رشته خاص ختم بشه. مثلاً به aba ختم بشه که در این صورت k=3 میشه. جوابش فکر کنم گزینه ۴ باشه. ۱و۳ که درستن و ۲ رو هم میشه تمام حالات مکمل k حرف آخر درنظر گرفت. ولی گزینه ۴ باید نال رو قبول کنه؛ میشه با ماشین متناهی طراحی کرد ولی فکر نکنم بسته بودنشو ثابت کنه.
دوست عزیز، اینی که من می گم در مورد گزینه اول سوال ۵۶ درسته؟
ما یه تعداد a,b داریم که با هم برابرند. دزست؟
حالا در کنارش یا یه a داریم یا یه b. میتون مبگم زبانم بصورت زیر هست؟
[tex]a^{n}b^{n}a \bigcup a^{n}b^{n}b[/tex]
حالا برای این عبارت بالا میشه NFA طراحی کرد؟!!! چطوری؟
فکر کنم به ستاره بالای (a+b) توجه نکردین. ما یه تعداد a,b با هم برابر داریم ولی این تعداد میتونه صفر باشه. با صفر شدنش زبانمون سیکمااستار میشه و تمام رشته هارو قبول میکنه. گرامر زیرو به ازای مقادیر مختلف n قبول دارین؟
[tex](a b)^*\cup ab(a b)^*\cup a^2b^2(a b)^*\cup ... \cup a^nb^n(a b)^*[/tex]
جمله سمت چپ سیکمااستاره و بقیه زیرمجموعه اونن.
(۲۵ بهمن ۱۳۹۰ ۰۴:۰۸ ب.ظ)Lakikharin نوشته شده توسط: فکر کنم به ستاره بالای (a+b) توجه نکردین.
چه جالب!
من کلی پیش خودم فکر کردم که چرا قبلا این سوال رو بلد بودم ولی الان هر چی فکر می کنم و اطلاعاتمم کاملتر شده نمی تونم گزینه صحیح رو بزنم.
خیلی ممنونم
از روی کتابهای سنجش می خونم و الان دیدم استار رو نذاشته بود
متشکرم
(۲۵ بهمن ۱۳۹۰ ۱۲:۰۹ ق.ظ)Jooybari نوشته شده توسط: فکر کنم توی این بحث هنوز مشکل دارین. یکی از حالات در سوال ۵۶ برای این دو گزینه n=0 هست. با این حالت شما میتونین تمام حالات ممکن برای بقیه مقادیر n رو بسازید. یعنی زبان گزینه اول سیکما استار و زبان گزینه دوم b*a* میشه.
چرا زبان گزینه دوم برابر [tex]b^{\ast}a^{\ast}[/tex] است؟
زبان رشته های دیگری هم مانند ab و baba نیز تولید می کند که در [tex]b^{\ast}a^{\ast}[/tex] نیست