اول سوال دومت رو جواب میدم. چون اولی بنظرم بدیهیه. دلیلی براش ندارم فعلا..
قسمت ج سوال۲:
متمم یک زبان مثلL1 یعنی رشته هایی رو میخواهی بدست بیاوری که در این زبان نیست.
سه حالت پیش میاد برای این مورد:
۱- یا میای روی a ها بحث میکنی و تغییرات رو فقط روی a اعمال میکنی. به این ترتیب که در زبان L1 ، تعداد aها حداقل ۴ است، در زبان L متمم، باید تعدادaها حداکثر۴تا باشد.و b هر چه که میخواهد، باشد(میبینی که * برای b گذاشته) اینجوری قطعا این رشته ها جز L نخواهند بود ودر متممش خواهند بود. تا اینجا اولین عبارت منظم قسمت ج بدست آمد
۲- میتوانی فقط روی b ها بحث کنی. وهمانطور که میبینی در زبان L1 حداکثر۳ b داریم، حال در متممش باید حداقل ۴تا b داشته باشیم تابتوانیم رشته ای بدست اوریم که در متمم L باشد. در این حالت تعداد a مهم نیست. با این حساب عبارت منظم دوم قسمت ج هم بدست آمد.
توجه: در این دوحالت ترتیب قرار گرفتن ترمینال ها دقیقا مثل زبان L1 است. یعنی اول aها امده وبعد bها.
۳- اما در این حالت، ترتیب قرار گرفتن کلا بهم ریخته.یه پایه(ba) درنظر میگیریم که مطمئن شیم این رشته قطعا عضو L1 نخواهد بود.حالادیگه اول و اخر عبارت مهم نیست چی بیاد(میبینی که هم میتونهa بیاد هم b وهم ترکیبی از هردو با هرترتیبی).چون هرچه که باشه قطعا عضو زبانL1نیست. چون در زبان L1 اول a داریم وبعدb. اما در اینجا ترتیب به هم خورده. اینجوری شد که عبارت منظم سومی هم بدست اومد
برای قسمت د هم، دقیقا همین استدلال صادقه

سلام .برای سوال اول که این هستش : $(\lambda a)^{\ast}$
خب یعنی این که هر تعداد $\alpha$ رو خواستیم میتونیم کنار هم قرار بدیم و به عنوان خروجی بیاریم و همچنین چون $\lambda$ رو هم داریم پس این هم میتونه جزو جواب ما باشه .حالا میرسیم به قسمت های سمت راست که اولیش اینه
$(\lambda \alpha\alpha)^{\ast}$ که اگه دقت کنی میبینی که هم $\lambda$ جزو خروجی هستش و هم هر تعداد که خواستیم $\alpha$ تولید کردیم . از طرفی هم که میدونیم $(\alpha\alpha)^{\ast}=\alpha^$ هستش پس اینم قسمت دوم رو بهمون میده و حالا داریم $\lambda \alpha^$ یعنی که خروجی یا $\lambda$ هستش یا هر تعداد دلخواه $\alpha$ که این عبارت همون $\alpha^{\ast}$ هستش چون اینجا هم جواب یا $\lambda$ هستش یا هر تعداد مشخص $\alpha$

سلام
ببخشید *(a*=(λ+a
* λ+a+= λ+aa
در عبارت بالای میتونیم هیچ a رو نبینیم
اما در عبارت پایینی ما حداقل یک a رو میبینم پس چطوری امکان داره عبارت پایینی با عبارت بالای مساوی باشه؟

(۲۰ دى ۱۳۹۴ ۱۱:۳۹ ب.ظ)Alirezaj نوشته شده توسط:  سلام
ببخشید *(a*=(λ+a
* λ+a+= λ+aa
در عبارت بالای میتونیم هیچ a رو نبینیم
اما در عبارت پایینی ما حداقل یک a رو میبینم پس چطوری امکان داره عبارت پایینی با عبارت بالای مساوی باشه؟

سلام
ببینید تو عبارت منظم دوم هم لاندا داریم. + بین دوعبارت منظم حالت اجتماع ایجاد میکنه یعنی در عبارت منظم دوم یا لاندا تولید میشه یا حداقل یک a باید داشته باشیم و این درواقع یعنی همون لاندار استار