(۱۷ بهمن ۱۳۹۲ ۰۲:۰۳ ب.ظ)hosshah نوشته شده توسط:  

(17 بهمن ۱۳۹۲ ۱۲:۱۵ ب.ظ)fulgent نوشته شده توسط:  سلام
لطفا اگر سوال زیر تکراری است لینک بدین تا اینو حذف کنم.. و گرنه در حل آن راهنمایی بفرمایید.



به نظر خودم هم گزینه ۲ و هم گزینه ۴ . نظر دوستان چیه؟

گزینه ۱: در مورد مستقل از متن بودن این زبان بحث شده بود
گزینه ۲: اگر [tex]w\epsilon \{a,b\}^{*}[/tex] که زبانمون همون [tex]\sum ^{ }[/tex] میشد اما اینجوری باید بین دو رشته یا aa یا bb باشه که میشه با DFA تشخیص داد

گزینه ۳: این هم مستقل از متنه
گزینه ۴: شما اگر شک داری که این منظمه ببین میتونی هر طور که رشته رو شکسته این ww برقرار باشه؟ این زبان هم به نظرم حساس به متنه

(۱۷ بهمن ۱۳۹۲ ۰۲:۲۵ ب.ظ)sara_omd نوشته شده توسط:  من توی گزینه ٢ و٣ و ٤ باهات موافقم اما گزینه ی ١ رو شک دارم و فکر می کنم حساس به متنه آخه وقتی w با معکوسش نباید برابر باشه زبان هم منظم میشه هم مستقل از متن اما اینجا که w1 با w2 نباید مساوی باشه نه با معکوسش به نظرم حساس به متنه
در مورد گزینه ٢میشه بگی dfaش دقیقا چطوری میشه

(۱۷ بهمن ۱۳۹۲ ۰۲:۰۳ ب.ظ)hosshah نوشته شده توسط:  گزینه ۱: در مورد مستقل از متن بودن این زبان بحث شده بود
گزینه ۲: اگر [tex]w\epsilon \{a,b\}^{*}[/tex] که زبانمون همون [tex]\sum ^{ }[/tex] میشد اما اینجوری باید بین دو رشته یا aa یا bb باشه که میشه با DFA تشخیص داد

گزینه ۳: این هم مستقل از متنه
گزینه ۴: شما اگر شک داری که این منظمه ببین میتونی هر طور که رشته رو شکسته این ww برقرار باشه؟ (مثلا ab چجور میتونه ww باشه) این زبان هم به نظرم حساس به متنه

(۱۷ بهمن ۱۳۹۲ ۰۲:۴۲ ب.ظ)Jooybari نوشته شده توسط:  کاملاً موافقم.

(۱۷ بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)hosshah نوشته شده توسط:  

(17 بهمن ۱۳۹۲ ۰۲:۲۵ ب.ظ)sara_omd نوشته شده توسط:  من توی گزینه ٢ و٣ و ٤ باهات موافقم اما گزینه ی ١ رو شک دارم و فکر می کنم حساس به متنه آخه وقتی w با معکوسش نباید برابر باشه زبان هم منظم میشه هم مستقل از متن اما اینجا که w1 با w2 نباید مساوی باشه نه با معکوسش به نظرم حساس به متنه
در مورد گزینه ٢میشه بگی dfaش دقیقا چطوری میشه

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

این لینک رو چک کن واسه گزینه ۱ (
برای گزینه۲:
در حالت ۰ یه دونه a یا b ببین برو حالت ۱تو حالت ۱ با a,b رو خودش loop میزنه (u)
اگه aa یا bb دید میره به حالت بعد ([tex]ww^{r}[/tex] ، البته توی دو تا state این انجام میشه دیگه فقط گفتم یه دید کلی بدم)
در این حالت پهم یه دونه a یا b میبینه و میره به حالت پایانی و تو حالت پایانی هم با a,b رو خودش loop میزنه (v)
البته این NFAشه)

(۱۷ بهمن ۱۳۹۲ ۰۲:۱۲ ب.ظ)mahsalove نوشته شده توسط:  گزینه ۲ مستقل از متنه؟!
reverso که نمیشه با DFA تشخیص داد ولی بقیه رو درست گفتید!

(۱۷ بهمن ۱۳۹۲ ۰۲:۲۱ ب.ظ)hosshah نوشته شده توسط:  

(17 بهمن ۱۳۹۲ ۰۲:۱۲ ب.ظ)mahsalove نوشته شده توسط:  گزینه ۲ مستقل از متنه؟!
reverso که نمیشه با DFA تشخیص داد ولی بقیه رو درست گفتید!

ما که لازم نیست reverse رو تشخیص بدیم
ما کافیه فرضمون رو بر این بزاریم که طول رشته w برابره ۱ هستش

اونوقت [tex]WW^{R}[/tex] طولش ۲ هست و میتونه aa یا bb باشه

(۱۷ بهمن ۱۳۹۲ ۰۴:۰۶ ب.ظ)izadan11 نوشته شده توسط:  چرا زبان سوم منظم نیست ؟

(۱۷ بهمن ۱۳۹۲ ۱۰:۳۱ ب.ظ)Jooybari نوشته شده توسط:  

(17 بهمن ۱۳۹۲ ۰۴:۰۶ ب.ظ)izadan11 نوشته شده توسط:  چرا زبان سوم منظم نیست ؟

چون شرط [tex]n\neq k-1[/tex] رو نمیتونه بدون پشته چک کنه. این شرط همپوشانی با شرط قبلی هم نداره.

(۱۸ بهمن ۱۳۹۲ ۰۱:۱۴ ق.ظ)izadan11 نوشته شده توسط:  یک شرطش گفته n>k و دیگری گفته n<>k-1 در شرط دوم فقط یک حالت قبول نیست که در شرط اول پوشش داده شده پس گرامر ما میشه a^n .b^m
و n و m هیچ ربطی به هم ندارن

(۱۸ بهمن ۱۳۹۲ ۰۱:۳۱ ق.ظ)hosshah نوشته شده توسط:  

(18 بهمن ۱۳۹۲ ۰۱:۱۴ ق.ظ)izadan11 نوشته شده توسط:  یک شرطش گفته n>k و دیگری گفته n<>k-1 در شرط دوم فقط یک حالت قبول نیست که در شرط اول پوشش داده شده پس گرامر ما میشه a^n .b^m
و n و m هیچ ربطی به هم ندارن

من میگم کلا این هارو که ترکیب کنیم اون a^n.b^m که شما گفتی باید شرط n!=m-1 به هرحال برقرار باشه

(۱۸ بهمن ۱۳۹۲ ۰۱:۳۴ ق.ظ)izadan11 نوشته شده توسط:  لازم نیست
اشتراک نداریم که , اجتماع است

(۱۸ بهمن ۱۳۹۲ ۰۱:۳۸ ق.ظ)hosshah نوشته شده توسط:  

(18 بهمن ۱۳۹۲ ۰۱:۳۴ ق.ظ)izadan11 نوشته شده توسط:  لازم نیست
اشتراک نداریم که , اجتماع است

خب بالاخره یکی از این زبون ها باید تولیدش بکنه تا اجتماعش هم بتونه دیگه
اینکه n=m-1 باشه رو کدومشون میتونه تولید کنه؟

(۱۸ بهمن ۱۳۹۲ ۰۳:۰۸ ق.ظ)izadan11 نوشته شده توسط:  یعنی ما هر رشته ای به این فرم داشته باشیم جزو یکی از این دو مجموعه است پس ما کافی است چنین رشته ای رو تشخیص بدیم که dfa اون به راحتی قابل رسمه

(۱۸ بهمن ۱۳۹۲ ۰۳:۱۴ ق.ظ)hosshah نوشته شده توسط:  

(18 بهمن ۱۳۹۲ ۰۳:۰۸ ق.ظ)izadan11 نوشته شده توسط:  یعنی ما هر رشته ای به این فرم داشته باشیم جزو یکی از این دو مجموعه است پس ما کافی است چنین رشته ای رو تشخیص بدیم که dfa اون به راحتی قابل رسمه

خودت داری میگی ما هر رشته ای به فرم a^n.b^m بگیریم جزو یکی از این زبون ها هست دیگه حالا من میگم اینکه n=m-1 باشه جزو کدومشونه؟
شما میگی می میتونیم رشته ای تولید کنیم که تعداد b هاش یه دونه از a هاش بیشتر باشه. حالا سواله من اینه که با کدوم یکی از این زبان ها میخوای تولیدش کنی؟ خب وقتی هیچ کدوم از این زبان ها نتونه تولیدش کنه پس اجتماعش هم نمیتونه دیگه