اگه اشتباه نکنم هر دو مسئله جزء مسائل حل شده لینز است! البته این مسائل کلا" تشریحی است. فکر کنم نتایجشون مهمه!

۱-
زبان مورد نظر تک الفبایی است پس کافی است ثابت کنیم که مستقل از متن است( زبان تک الفبایی که مستقل از متن باشد منظم نیز هست )

می توانید برای آن یک گرامر مستقل از متن بنویسید.

---

[tex]S\rightarrow a^i A[/tex]
[tex]A\rightarrow a^K A|a^K[/tex]

برای رسم DFA هم به این صورت عمل کنید:

ابتدا از حالت شروع q0 با خواندن i تا a به وضعیت دیگری برسید qi سپس با خواندن k تا a به qi+k برسید سپس با لاندا به qi برگردید در اینصورت شما با خواندن i تا a و مضربی از k تا a به حالت پذیرش میرسید (همان qi+k )

چون j صفر نیز میتواند باشد از حالت qi با لاندا به qi+k بروید.(یا qi را نیز حالت پذیرش قرار دهید.)

---

۲- فکر کنم درست باشه چون برای متمم کردن کافی است که حالات پذیرش را به غیر پذیرش و حالات غیر پذیرش را به حالات پذیرش تبدیل کنیم که چون Q-F همان حالات غیر پذیرش است که در L' به عنوان حالات پذیرش معرفی شده یعنی F‌ها هم اکنون غیر پذیرش است و این همان متمم کردن است.

نکته مهم این است که DFA داشتیم و مینیمال شده بود (اگر مینیمال نبود متمم اش منحصر به فرد نبود).

(اگر NFA بود مطالب بالا صادق نبود)

اگه جایی ابهام یا اشکال داره بهم بگین.