(۲۶ آبان ۱۳۸۹ ۱۰:۱۱ ق.ظ)saba_1984 نوشته شده توسط:  سلام

من یه تصویر اینجا میگذارم که چند تا سوال نظریه رو نشون میده که سوالات کنکور دوم پارسه هست.



پارسه جواب سوال ۵۸ رو یک اعلام کرده که از نظر من ۴ صحیحه و جواب سوال سوال ۶۱ رو هم دو اعلام کرده که من نمیدونم چرا ؟ و اینکه چرا ۳ صحیح نیست .

نظر شما چیه؟


این جمله هم تو کتاب پارسه هست صفحه ۸۰:

"برای هر DFA با چندین وضعیت ابندایی یک DFA با یک وضعیت ابتدایی وجود دارد"

این جمله درسته؟

منم با شما موافقم به نظر سوال ایراد داره به حالت زیر دقت کنید
N=bb
M=aMa
M=aNa
N= aa
در کل داریم‌:
bbM
bbaMa
bbaaNaa
bbaaaaaa
شاید سوال اشکال داشته باشه(مطمئن نیستم)
اما برای هر NfA یه NFA معادل با یه حالت نهایی وجود داره(پوران صفحه۹۲ چاپ ۸۷). و از اونجایی که هر DFA یه NFA هست (بر عکسش غلطه) پس برای هر DFA یه DFAبا یه حالت نهایی وجود داره.

(۲۶ آبان ۱۳۸۹ ۱۰:۱۱ ق.ظ)saba_1984 نوشته شده توسط:  سلام

من یه تصویر اینجا میگذارم که چند تا سوال نظریه رو نشون میده که سوالات کنکور دوم پارسه هست.



پارسه جواب سوال ۵۸ رو یک اعلام کرده که از نظر من ۴ صحیحه و جواب سوال سوال ۶۱ رو هم دو اعلام کرده که من نمیدونم چرا ؟ و اینکه چرا ۳ صحیح نیست .

نظر شما چیه؟


این جمله هم تو کتاب پارسه هست صفحه ۸۰:

"برای هر DFA با چندین وضعیت ابندایی یک DFA با یک وضعیت ابتدایی وجود دارد"

این جمله درسته؟

جواب ۱ درسته چون گزینه ۳و ۴ عبارت با طول ۲رو قبول میکنند که درست نیس حداقل طول باید ۶باشه ...کوتاهترین جمله aabbaa میشه مثلا(u وw هرکدوم ۲تا و چون a,b + خورده از v ,vR هم یکی که کلا میشه ۶ تا). پس یا ۱ باید باشه یا ۲ که با تست چند مورد متوجه میشیم ۱ میشه

برای قسمت دوم سوالتون هم درسته ... میشه یک وضعیت S1 بدون وارد شدن ایرادی به مسئله ایجاد کرد که حالت های مختلف اول به حالت S1 برن

(۲۶ آبان ۱۳۸۹ ۰۵:۱۴ ب.ظ)saria نوشته شده توسط:  

(26 آبان ۱۳۸۹ ۱۰:۱۱ ق.ظ)saba_1984 نوشته شده توسط:  سلام

من یه تصویر اینجا میگذارم که چند تا سوال نظریه رو نشون میده که سوالات کنکور دوم پارسه هست.



پارسه جواب سوال ۵۸ رو یک اعلام کرده که از نظر من ۴ صحیحه و جواب سوال سوال ۶۱ رو هم دو اعلام کرده که من نمیدونم چرا ؟ و اینکه چرا ۳ صحیح نیست .

نظر شما چیه؟


این جمله هم تو کتاب پارسه هست صفحه ۸۰:

"برای هر DFA با چندین وضعیت ابندایی یک DFA با یک وضعیت ابتدایی وجود دارد"

این جمله درسته؟

جواب ۱ درسته چون گزینه ۳و ۴ عبارت با طول ۲رو قبول میکنند که درست نیس حداقل طول باید ۶باشه ...کوتاهترین جمله aabbaa میشه مثلا(u وw هرکدوم ۲تا و چون a,b + خورده از v ,vR هم یکی که کلا میشه ۶ تا). پس یا ۱ باید باشه یا ۲ که با تست چند مورد متوجه میشیم ۱ میشه

برای قسمت دوم سوالتون هم درسته ... میشه یک وضعیت S1 بدون وارد شدن ایرادی به مسئله ایجاد کرد که حالت های مختلف اول به حالت S1 برن

حرف شما برا رد گزینه ۳و ۴ درسته ولی اثبات شما برا گزینه ۱ چیه ؟

شما در ابتدای جمله یک رشته با طول ۲ دارید( u )بعد از قانون M به رشته ای می رسید که اول و آخرش یکی هست ولی وسطش دیگه لزوما اینگونه نیست مثلا ممکنه رشته ab،aa،ba رو داشته باشید u=ab , v=a,vR=a,w=ab یعنی u و W از قانون N که طول اون دقیقا ۲ هست بدست میاد و V,VR از قانون M که میتونه طول بینهایت داشته باشه.

نکتش اینه که شما باید قانون رو با حروف پایانی بدست آمده از N خاتمه بدین به خاطر همین طول W دقیقا ۲ است ولی طول V متغیر چون قانون M میتونه یه قانون بازگشتی باشه اگر چه در آخر باید به یکی از سمت راستی های N ختم بشه( W)
مثلا رشته ab،bbb،ba،bbb (‌، بین رشته‌ها برای مشخص کردن u,v,.... است). که اینجا طول V از ۲ بیشتره.)۳)

البته سوال ساده نیست است ولی از روی طول قوانین N میشه دو گزینه آخر رو حذف کرد و گزینه ۳ هم با یه مثال نقض و دقت به قانون M رد میشه.

سوال ۵۸ من این وسط یه نظر بدم اگه قراره شک کنیم باید بین ۱ و۲ شک کنیم چون u,w هیچوقت نمیتونن عضو *[a,b] باشند
سوال ۶۱-این شوال دقیقا از تو حل التمرین کتاب لینز طرح شده و تا جایی که من یادمه همون گزینه۲ صحیح هستش فقط بجای T اینجا P گذاشتند بازم من دقیق حضور ذهن ندارم اما خوب اعلام میکنم

در مورد سوال ۶۱:
ببین این تو اثبات قضیه ۲-۵ لینز اومده.
همون ۲ درسته.

در مورد سوال ۶۱ تو کتاب لینز دیدم و تو کتاب پارسه هم نکته وار این مساله رو گفته‌، ولی من هیچ دلیلی واسه این مطلب نداشتم . میخواستم بدونم توجیه خاصی داره ؟
یا همینطور حفظ کنم(بپذیرم)؟ 

(۲۸ آبان ۱۳۸۹ ۰۶:۵۶ ب.ظ)saba_1984 نوشته شده توسط:  در مورد سوال ۶۱ تو کتاب لینز دیدم و تو کتاب پارسه هم نکته وار این مساله رو گفته‌، ولی من هیچ دلیلی واسه این مطلب نداشتم . میخواستم بدونم توجیه خاصی داره ؟
یا همینطور حفظ کنم(بپذیرم)؟ 

فصل ۵ قضیه ۲-۵ کتاب لینز کمکت میکنه

(۲۸ آبان ۱۳۸۹ ۰۶:۵۶ ب.ظ)saba_1984 نوشته شده توسط:  در مورد سوال ۶۱ تو کتاب لینز دیدم و تو کتاب پارسه هم نکته وار این مساله رو گفته‌، ولی من هیچ دلیلی واسه این مطلب نداشتم . میخواستم بدونم توجیه خاصی داره ؟
یا همینطور حفظ کنم(بپذیرم)؟ 

نمیخواد زیاد کنجکاوی کنی و مسائل رو اثبات کنی اینا قبلا اثبات شده برای این مثال بهتره یه نمونه از خودت بنویسی ببینی این قضیه درسته یانه که حتما درسته و گرنه جناب لینز نمی آورد تو کتابش
شما همینجوری بپذیر!!!!!