سلام. سوال ۶۲ همه منظمن. توی اینجور سوالات باید سعی کنید با مقدار دهی به آلفا و بتا و گاما و توانها یه جوری زبان رو تعریف کنید که به ازای تمام رشته های با طول بزرگتر از یه حدی جواب بده. یا اینکه به ازای یه توانی تمام رشته های زبان در اون توان هم تولید بشه. یعنی بقیه توانها و حالات زیرمجموعه ای از اون حالت باشن.
L1:
i=1 , j=0 و گاما=نال و آلفا = سیکمااستار زبان سیکمااستار میشه.

L2:
i=1 , j=0 و گاما=نال و آلفا = سیکمااستار زبان سیکمااستار میشه.

L3:
i=j=1 و آلفا و گاما = نال و بتا = سیکماپلاس زبان سیکماپلاس میشه.

سوال ۵۸ که گرامر داره گزینه ۱ میشه:
یه رشته از زبان L1 میشه aaabbbbbbaaa که گرامر تولید نمیکنه. (اگه گرامر زبان L1 رو دیده باشید میدونید گرامر G چه قواعدی کم داره و چه رشته هایی رو نمیتونه تولید کنه.)
دوتا رشته برای زبان L2 که نشون بده این زبان کلاً از جواب پرته: aaa رو میپذیره و aaabbb رو نمیپذیره.

سوال ۵۶: گزینه ۲
گزینه ۱ توان رو برابر ۰ میگیریم. منظم میشه.
گزینه ۲ توان رو برابر ۰ بگیریم منظم نمیشه. چون بقیه حالات زیرمجموعه این حالت نیست.
گزینه ۳ توان رو برابر ۰ میگیریم. منظم میشه.

سوال ۵۸ اون یکی:
L1:
توان رو برابر ۱ میگیریم و زبان میشه سیکمااستار.

L2:
منظمه. برای A ماشین متناهی داریم و حالاتی که نباید از اونا رد بشیم رو تله درنظر میگیریم و ماشین جدید میسازیم.

L3:
(نیازی به اثبات منظم بودنش نیست. از روی گزینه ها میشه تشخیص داد.) ماشین متناهی نیاز به یه حافظه متناهی مشخص داره که میشه پیاده سازی کرد.