با سلام خدمت دوستان سوال عکس زیر جوابش گزینه ی یک هست ( از روی دو منبع مختلف نگاه کردم هر دو گزینه ی یک رو زدن) ولی اصلا نمیفهمم چرا یک درسته.... هرجوری حساب میکنم هیچ گزینه ای درست نیست
![[تصویر: 361913_4qug_n89.png]](https://img.manesht.ir/361913_4qug_n89.png)
سلام
گزینه ی یک صحیح است
زبان داده شده در صورت سوال متشکل از سه نوع رشته است:
دسته اول
[tex](\lambda a aa aaa)b^{\ast}[/tex] به معنای تمام رشته هایی است که در ابتدا حداکثر سه a دارند و بعد هیچی یا چند تا b در ادامه دارند
دسته دوم
[tex]a^{\ast}bbbbb^{\ast}[/tex] که به معنای تمام رشته هایی است که در ابتدا هیچ یا تعدادی a داند وبعد از آن حداقل ۴تا b دارند
دسته سوم
[tex](a b)^{\ast}ba(a b)^{\ast}[/tex] (البته تو سوال روی پرانتز دوم استار نداره که باید داشته باشه و اگه استار نداشته باشه هیچ گزینه ای صحیح نیست)
این دسته شامل تمام رشته هایی هستند که حداقل یک زیر رشته ی ba دارند یعنی حداقل در یک قسمتی از رشته b قبل از a ظاهر می شود.
حالا مکمل زبان گزینه ی اول را حساب کنیم
خود زیان می گه حتما تعداد a ها بزرگتر مساوی ۴ و حتما تعداد b ها باید کمتر مساوی ۳ باشه
نقیض آن می شه: رشته هایی که تعداد a ها کمتر ۴ (یعنی کمتر مساوی ۳: همون ردشته ی اولی که در بالا توضیح دادم) یا تعداد b ها باید بیشتر از ۳ (یعنی بیشتر مساوی ۴: همون دشته ی دوم) باشه
پس نقیض عبارت مطرح شده در زبان گزینه ی ی را می توان در رشته های دسته ی اول و دوم زبان مطرح شده در صورت سوال دید.
اما این دو دسته تمام زیان مکمل گزینه ی ۱ را تشکیل نمی دهند. چون معنای مکمل یک زیان یعنی تمام رشته هایی که در آن زیان نیستند مثلا در زیان گزینه ی ۱ همه ی رشته ها حتما بیشتر مساوی از ۴ تا a دارند پس همه ی رشته های با تعداد a های کمتر مساوی ۳ در مکمل این زبان هستند یا مثلا در زیان گزینه ی ۱ همه ی رشته ها حتما کمتر مساوی از ۳ تا b دارند پس همه ی رشته های با تعداد b های بیشتر مساوی ۴ در مکمل این زبان هستند
یا مثلا در همه ی رشته های زبان گزینه ی ۱ در ایتدا اول a ها آمده اند و بعد b ها و هیچ a ای حق ظاهر شدن بعد از b ها را ندارند . پس تمام رشته هایی که در آن ها حداقل یک بار یه a بعد از b ظاهر می شه در مکمل این زبان قرار دارند که همان رشته های دسته سوم هستند.
گزینه ۲ غلطه: چون هر دو رشته [tex]\lambda[/tex] رو تولید میکنن. پس نمیتونن مکمل هم باشن.
گزینه ۳ غلطه: چون این زبان رشته [tex]ba[/tex] رو تولید نمیکنه.
گزینه ۴ غلطه: چون این زبان رشته [tex]ba[/tex] رو تولید نمیکنه.
در توضیح گزینه ۱ :
قبل از هر چیز نمودار مربوطه به عبارت منظم [tex]aaaa(a)^{\ast}(\lambda b bb bbb)[/tex] را رسم میکنیم:
و حالا مکمل این زبان که در شکل دوم نمایش داده شده است:
و با تطبیق عبارت منظم و [tex]dfa[/tex] نهایی به نتیجه مطلوب میرسیم. البته مقایسه این دو (برابری زبان [tex]dfa[/tex] نهایی و زبان حاصل از عبارت منظم صورت سوال سخت است )
بهترین و راحتترین کار برای اینگونه سوالات رد کردن گزینه هاست.