۱)نشان دهید که زبان
[tex]l={a^{n}n=i jk;i, k are fixed ;j=0,1,2,...}[/tex]
منظم است
۲)فرضیه زیر را ثابت و یا رد کنید.
اگر [tex]M=(Q,\sum ,\delta ,q_{0},F)[/tex]
یک dfa کاهش یافته برای زبان منظم L باشد و یا آنگاه dfa مانند M1 با تابع [tex]\delta _{1}[/tex]
و وضعیت اولیه [tex]_{q_{0}}[/tex]
با [tex]\widehat{M}[/tex]
معادل و دارای [tex]\widehat{M}= {Q,\sum ,\delta ,q_{0},Q-F}[/tex]
یک dfa کاهش یافته برای [tex]L'[/tex]
است
اگه اشتباه نکنم هر دو مسئله جزء مسائل حل شده لینز است! البته این مسائل کلا" تشریحی است. فکر کنم نتایجشون مهمه!
۱-
زبان مورد نظر تک الفبایی است پس کافی است ثابت کنیم که مستقل از متن است( زبان تک الفبایی که مستقل از متن باشد منظم نیز هست )
می توانید برای آن یک گرامر مستقل از متن بنویسید.
[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 بود مطالب بالا صادق نبود)
اگه جایی ابهام یا اشکال داره بهم بگین.