سلام. dfa سوال اول شکل ۱ میشه. نیازی به ترکیب nfaها نبود. سوال دوم و سوم هم برای راحتی میتونید dfa هردو عبارتو بنویسید. بعد به اجتماع و اشتراک تبدیل کنید. یعنی ترکیب هردو ماشین رو بسازید. حالت هایی که در هردو ماشین حالت پایانی هستن اشتراک و حالت هایی که در حداقل یکی از ماشینها پایانی باشد اجتماع میشه. شکل ۲ و ۳ بترتیب dfa قسمت چپ و راست سوالات ۲ و ۳ هست. شکل ۴ و ۵ هم بترتیب اشتراک و اجتماع هستن.
مراحل کار برای ساخت اشتراک و اجتماع:
۱- تمام حرکات همزمان دو ماشن رو میسازیم؛ هر حالت از p و q تشکیل میشه.
۲- اشتراک حالتیه که وضعیت هایی که در هردو ماشین پایانیه رو پایانی بگیریم و اجتماع حالتیه که وضعیت هایی که در هریک از دو ماشین پایانیه رو پایانی بگیریم.
اگه سوالی داشتید در خدمتم.

سلام. ببینید عبارت بفرم $((p)^* (q)^*)$ هست. یعنی یا $(p)^*$ و یا $(q)^*$. nfa این زبان خیلی سادست. ولی dfaش یکم دردسر داره. بخاطر تولید رشته هایی که تا یه جایی مشابه هر دو قسمتن. توی سوال ۲ از روی دو حرف اول ورودی مشخص میشه باید $(abab)^*$ انخاب بشه یا $(aaa^* b)^*$. ولی نمیشه یکی از این انتخاب بشه و یکی از اون. مثلاً رشته $aaaababab$ پذیرفته نیست. اگه اول رشته $ab$ دریافت شد از این به بعد فقط باید یه تعداد فرد دیگه $ab$ بیاد. اگه اول $aa$ یا $b$ بیاد فقط باید پرانتز دوم انتخاب بشه و توی رشتمون فقط باید یه تعداد $b$ و یا هر تعداد حداقل دوتا $a$ داشته باشیم. این سوالو هم میشه با روشی مشابه سوال ۲ و ۳ حل کرد ولی میبینید که رشته های دو قسمت کاملا از دو حرف اول قابل تشخی هستن و نیاز به ترکیب دو ماشین نیست. اینکه یکم بزرگ شده بخاطر طول رشته های حالت $(abab)^*$ هست. وگرنه nfaش رو میشه با ۹ حالت کشید.
برای سوالات ۲ و ۳ هم باید دو تا dfa رو با هم بکشید. حالت شروع توی یکی p0 و توی یکی دیگه q0 میشه حالت شروع توی ماشین اجتماع یا اشتراک میشه p0q0 حالا به ازای تمام حالت هایی که یالی با حرف a یا b خارج نشده این یال رو اضافه میکنیم. به عبارت دیگه سعی میکنیم dfa این ماشینو بکشیم. مسلماً تعداد حالت های این ماشین از حاصل تعداد حالات دو ماشین قبل بیشتر نمیشه. برای مثال از p0 با a به p1 و از q0 با a به q1 میریم. پس از p0q0 با a به p1q1 میریم. از p0 با b به p3 و از q0 با b به q2 میریم. پس از p0qp با b به p3q2 میریم. همین کارو با p1q1 و p3q2 ادامه بدید تا هیچ حالت جدیدی ایجاد نشه. اشتراک و اجتماعشم که مشخصه چجوریه.