تالار گفتمان مانشت
زبان های منظم- مهندسی کامپیوتر- ۸۹ - نسخه‌ی قابل چاپ
زبان های منظم- مهندسی کامپیوتر- ۸۹ - dokhtare payiz - 01 اردیبهشت ۱۳۹۵ ۰۹:۳۱ ق.ظ

چرا گزینه ۲ درسته؟

RE: زبان های منظم- مهندسی کامپیوتر- ۸۹ - mahyamk - 01 اردیبهشت ۱۳۹۵ ۱۰:۰۵ ق.ظ

(۰۱ اردیبهشت ۱۳۹۵ ۰۹:۳۱ ق.ظ)dokhtare payiz نوشته شده توسط:  چرا گزینه ۲ درسته؟

این سوال هر سه گزینه اش غلطه
لم تزریق فقط برای زبان های نامتناهی کاربرد داره ینی اگه این لم رو برای زبان های متناهی به کار ببرین غلط میشه
مثلا زبان رو بگیرین {aaa}
حالا اگه هر i بزرگتر از ۱ در نظر بگیرین رشته هایی تولید میکنه که در زبان نیست و میگه زبان ال ما منظم نیست ! در صورتی که هست!
پس گزینه ۱و۳ اینجا غلط هستن
گزینه ۲ ، فرض کنید زبان منظم و متناهی رشته ای به طول ۵ داشته باشه به ازای k ایی این جمله صدق نمیکنه چون فقط زبان ی رشته داره!
هیچ جواب درستی نداره

RE: زبان های منظم- مهندسی کامپیوتر- ۸۹ - Iranian Wizard - 02 اردیبهشت ۱۳۹۵ ۱۲:۴۷ ب.ظ

(۰۱ اردیبهشت ۱۳۹۵ ۱۰:۰۵ ق.ظ)mahyamk نوشته شده توسط:  
(01 اردیبهشت ۱۳۹۵ ۰۹:۳۱ ق.ظ)dokhtare payiz نوشته شده توسط:  چرا گزینه ۲ درسته؟
این سوال هر سه گزینه اش غلطه
لم تزریق فقط برای زبان های نامتناهی کاربرد داره ینی اگه این لم رو برای زبان های متناهی به کار ببرین غلط میشه
مثلا زبان رو بگیرین {aaa}
حالا اگه هر i بزرگتر از ۱ در نظر بگیرین رشته هایی تولید میکنه که در زبان نیست و میگه زبان ال ما منظم نیست ! در صورتی که هست!
پس گزینه ۱و۳ اینجا غلط هستن
گزینه ۲ ، فرض کنید زبان منظم و متناهی رشته ای به طول ۵ داشته باشه به ازای k ایی این جمله صدق نمیکنه چون فقط زبان ی رشته داره!
هیچ جواب درستی نداره
من نسبت به جواب درست این سوال شک دارم.
گزینه های ۱و۳ که به وضوح غلطه.ولی گزینه ۲ بنظر من میتونه درست باشه.
چرا که گزینه ۲ از یک عبارت شرطی استفاده کرده،و اگر فرض ما غلط باشه،جواب ترکیب شرطی همواره درست میشه.
در گزینه ۲: اگر زبان منظم نامتناهی باشه،که k همان تعداد حالات DFA پذیرنده اون زبان هستش. این جمله درست میشه.
و اگه زبان ما متناهی باشه،خب اگه k رو برابر طول بزرگترین رشته در نظر بگیریم،اونوقت همواره فرض غلط میشه(چون رشته ای به طول بزرگتر از k وجود نداره)،و در نتیجه جواب ما همواره درست خواهد بود.

اگه جواب من اشتباه هستش،لطفا واسم توضیح بدید،که اشتباهمو در تحلیل این سوال متوجه بشم.

RE: زبان های منظم- مهندسی کامپیوتر- ۸۹ - Jooybari - 02 اردیبهشت ۱۳۹۵ ۰۱:۰۰ ب.ظ

(۰۲ اردیبهشت ۱۳۹۵ ۱۲:۴۷ ب.ظ)IranianWizard نوشته شده توسط:  ...خب اگه k رو برابر طول بزرگترین رشته در نظر بگیریم،اونوقت همواره فرض غلط میشه(چون رشته ای به طول بزرگتر از k وجود نداره)،و در نتیجه جواب ما همواره درست خواهد بود.

سلام. وقت بخیر.
تو صورت سوال گفته برای هر زبان همواره یک k وجود داره. مثلاً برای زبان [tex]L=\{aaaa,aaab,aabb,abbb,bbbb\}[/tex] باید چنین k ای پیدا کنیم.

RE: زبان های منظم- مهندسی کامپیوتر- ۸۹ - Iranian Wizard - 02 اردیبهشت ۱۳۹۵ ۰۳:۱۲ ب.ظ

(۰۲ اردیبهشت ۱۳۹۵ ۰۱:۰۰ ب.ظ)Jooybari نوشته شده توسط:  
(02 اردیبهشت ۱۳۹۵ ۱۲:۴۷ ب.ظ)IranianWizard نوشته شده توسط:  ...خب اگه k رو برابر طول بزرگترین رشته در نظر بگیریم،اونوقت همواره فرض غلط میشه(چون رشته ای به طول بزرگتر از k وجود نداره)،و در نتیجه جواب ما همواره درست خواهد بود.
سلام. وقت بخیر.
تو صورت سوال گفته برای هر زبان همواره یک k وجود داره. مثلاً برای زبان [tex]L=\{aaaa,aaab,aabb,abbb,bbbb\}[/tex] باید چنین k ای پیدا کنیم.
سلام.ممنون از پاسختون.حرفتون کاملا درسته.ولی منم مثل صورت سوال فک میکنم خب میشه چنین kیی رو پیدا کرد،مثلا اگه زبان منظم نامتناهی باشه،خب k میشه تعداد حالات DFA . و اگه زبان منظم ما متناهی باشه،خب باز میتونیم چنین kیی رو پیدا کنیم که باعث بشه فرض سوال(یعنی اگر رشته ای به طول بزرگتر از k داشته باشیم) غلط بشه،و جواب ما به دلیل اینکه فرضش غلطه، همواره درست باشه.
مثلا همین زبانی که نوشتید،من اگه k=4 قرار بدم،خب چونکه رشته ای بزرگتر از ۴ وجود نداره،پس فرض سوال غلطه و به همین دلیل جواب همواره درست خواهد بود.یعنی میشه برای هر زبان متناهی چنین kیی رو پیدا کنیم که فرض ما رو نادرست کنه و در نتیجه عبارت شرطی ما درست بشه.

RE: زبان های منظم- مهندسی کامپیوتر- ۸۹ - Jooybari - 02 اردیبهشت ۱۳۹۵ ۰۳:۵۵ ب.ظ

(۰۲ اردیبهشت ۱۳۹۵ ۰۳:۱۲ ب.ظ)IranianWizard نوشته شده توسط:  
(02 اردیبهشت ۱۳۹۵ ۰۱:۰۰ ب.ظ)Jooybari نوشته شده توسط:  
(02 اردیبهشت ۱۳۹۵ ۱۲:۴۷ ب.ظ)IranianWizard نوشته شده توسط:  ...خب اگه k رو برابر طول بزرگترین رشته در نظر بگیریم،اونوقت همواره فرض غلط میشه(چون رشته ای به طول بزرگتر از k وجود نداره)،و در نتیجه جواب ما همواره درست خواهد بود.
سلام. وقت بخیر.
تو صورت سوال گفته برای هر زبان همواره یک k وجود داره. مثلاً برای زبان [tex]L=\{aaaa,aaab,aabb,abbb,bbbb\}[/tex] باید چنین k ای پیدا کنیم.
سلام.ممنون از پاسختون.حرفتون کاملا درسته.ولی منم مثل صورت سوال فک میکنم خب میشه چنین kیی رو پیدا کرد،مثلا اگه زبان منظم نامتناهی باشه،خب k میشه تعداد حالات DFA . و اگه زبان منظم ما متناهی باشه،خب باز میتونیم چنین kیی رو پیدا کنیم که باعث بشه فرض سوال(یعنی اگر رشته ای به طول بزرگتر از k داشته باشیم) غلط بشه،و جواب ما به دلیل اینکه فرضش غلطه، همواره درست باشه.
مثلا همین زبانی که نوشتید،من اگه k=4 قرار بدم،خب چونکه رشته ای بزرگتر از ۴ وجود نداره،پس فرض سوال غلطه و به همین دلیل جواب همواره درست خواهد بود.یعنی میشه برای هر زبان متناهی چنین kیی رو پیدا کنیم که فرض ما رو نادرست کنه و در نتیجه عبارت شرطی ما درست بشه.

ببینید برای هر زبان باید یه همچین k ای وجود داشته باشه. من یک زبان مثال زدم که برای اون چنین k ای وجود نداره.