(۰۴ شهریور ۱۳۹۱ ۰۲:۱۵ ب.ظ)shima_24 نوشته شده توسط: هوش به نظرتون راهیان خوبه بگیرم یا نه؟ از هوش پوران خوشم نمیاد.راهیان رو نمیدونم ولی کتاب راسل ترجمه راحتی خوبه.....پوران هم همش بد نیس بعضی جاهاش رو باید بیخیال شد چون خیلی مسخره است توضیح اضافه داده..در کل از بچه هایی دیگه هم مشورت بگیر
(۰۴ شهریور ۱۳۹۱ ۰۲:۰۱ ب.ظ)esisonic نوشته شده توسط:(04 شهریور ۱۳۹۱ ۰۸:۳۸ ق.ظ)skygirl_00 نوشته شده توسط: مثلا زبان ( a^n b^n ) و n بزرگتر مساوی ۰ببینید...
میشه کامل لم تزریقو روون توضیح بدین رو مثالش؟ y چطور انتخاب میشه. ....
لم تزریق میگه اگه بشه یه رشته w از یه زبان رو به ۳ قسمت تقسیم کنی به طوری که رشته بزرگتر مساوی n باشه و :
w=xyz و طول xy کوچکتر مساوی n باشه و اندازه ی y همواره بزرگتر از صفر باشه. همیشه باید رشته xyz از زبان مورد نظر نشأت گرفته باشه...
این روش فقط برای تشخیص منظم یا نامنظم بودن زبان استفاده میشه
مثلا ً زبان بالا رشته ی aabb یا aaaabbbb رو تولید می کنه که با قوانین بالا سازگار نیست...پس این زبان نا منظم است
زیاد هم تو کنکور مهم نیست...مگر از مفهوم روش سوأل بیاد...چون روش های سریع تری برای تشخیص زبان هست
مرسی از جوابتون. اما لطف کنید رو همین مثال بالا xy و y ازین چیزا رو بگین... که y رو تو مثال باید چی بگیریم.. تو کتاب میگه زیر رشته y باید فقط از a تشکیل بشه . [tex]| y |=k[/tex] و m=n گرفته... متوجه نمیشم اصلا!!!! اینا چی ان؟
من رو مثال می خوام متوجه بشم. گیر کردم
در مورد مفهوم لم تزریق یه مقدار توضیح میدم. لم تزریق (شماره ۱) برای رد منظم بودن یه زبانه. یعنی نشون بدیم یه زبان منظم نیست؛ نه اینکه اثبات کنیم یه زبان حتماً منظمه.
هر زبان منظم با dfa قابل پیاده سازیه. حالات هر dfa هم محدوده. فرض کنید تعداد حالات یک dfa برابر n باشه. پس هر رشته با طول بزرگتر از n حتماً حداقل یک دور توی n+1 حرف اولش داره. یعنی از یکی از حالت های dfa حداقل دوبار عبور کرده.
ما یه M که از n بزرگتره دو درنظر میگیریم. پس رشته هایی که حداقل طول M رو دارن حتماً توی یه جایی از یه حلقه (توی dfaشون) عبور کردن. اون حلقه قسمتی از رشتست که با y مشخص میشه و طول حلقه هم طبیعتاً ۰ نمیتونه باشه. (البته میتونه شامل چند دور باشه که باز هم فرقی نمیکنه.) پس با حذف و یا تکرار رشته ای که توی حلقه افتاده نباید مشکلی در پذیرش وجود داشته باشه.
توی لم تزریق میگیم "نتونستیم هیچ جایی برای این حلقه پیدا کنیم. پس منظم نیست." یعنی با تغییر مکان x و y و z از رشته xyz و با شرط اینکه xy از M بزرگتر نباشه (یعنی حلقه y در M حرف اول وجود داشته باشه،) هیچ زیر رشته y پیدا نشد که نقش حلقه رو داشته باشه.
برای مثالتون میگیم رشتمون هست {a^{M}b^{M که M یه عدد بزرگیه که مسلماً از تعداد حالت های dfa ماشین فرضیمون بیشتره. این رشته جزء زبانه و مسلماً باید در M حرف اولش یه جایی یه حلقه ای بنام y وجود داشته باشه. توی این رشته با این انتخاب مثال از زبان، زیر رشته y فقط شامل یه تعداد a میشه. این تعداد رو k در نظر میگیریم و چون y در M حرف اول رشتست طولش بین ۱ و M خواهد بود. چون xyz جزء زبانمونه پس xyyz هم باید جزء زبانمون باشه. این رشته میشه {a^{M+k}b^{M که جزء زبان نیست. پس نتونستیم هیچ زیررشته y پیدا کنیم که با تکرارش تمام رشته های بفرم xy^{i}z هم جزء زبان باشن. پس هیچ dfaی وجود نداره که این زبانو بپذیره و این زبان منظم نیست.
هرجایی از این تعریف هارو مشکل داشتید بگید تا بیشتر توضیح بدم.
من لم تزریق رو اینجوری استدلال میکنم که یه کاری انجام بدیم که مثلا نظم رشته بدست اومده از زبان بهم بخوره...مثلا اگه تعداد a باید با b برابر باشه کاری کنیم که a<b بشه یا برعکس...یعنی با تعدادی که برای x,y,i در نظر میگیریم...اگه تونستیم برای یک مورد هم اینکارو کنیم پس زبان منظم نیست
آقای جویباری این استدلالم درسته یا نه؟
این هفته قراره مدار منطقی بخونم . آسونه
(۰۳ شهریور ۱۳۹۱ ۱۱:۰۸ ب.ظ)skygirl_00 نوشته شده توسط: من امروز ۰ صفحه خوندم.... و همش میچرخیدم دور خودم... قرارم ندارم ک جمعه ها نخونم.اما خود ب خود ی روز در هفته همچین میشه. خیلی عذاب وجدان گرفتم همون ظهر،اما بازم سراغ کتاب نرفتم هی الان هی دو ساعت دیگه... تا الان. انقدر نگرانم که انگار ۱۰۰۰ تا اتفاق ناگوار پیش اومده... قلبم داره می یاد تو دهنم.منم زیاد ک واس کنکور آماده نیستم.....!!!! نمیدونم چرا دارم اینجا مینویسم اینارو؟؟؟
مشاور من یک روز درس خوندن توی هفته رو حرام کردن و میگن اگر بعد از ۶ روز یک روز به طور کامل استراحت نکنی و به تفریح و گردشت نرسی یهویی یک هفته میگذره و هیچی درس نمیخونی .
پس یک روز در هفته رو به خودت استراحت بده و به تفریح و گردشت برس که دوباره هفته بعدی رو با قدرت و ارامش بیشتری شروع کنی
من الان فصل اول قدسی رو تموم کردم .
خیلی کتاب جالبیه .
تا حالا البته با درس هایی که قبلا خوندم ، این درسهایی رو که مینویسم کامل خوندم
معماری : یه دور پترسون
نظریه : لینز با تمرینات
مدار منطقی : از قبل تسلط داشتم . پوران کافی بود
گسسته : گریمالدی با تمرینات . البته از قبل مطالعه داشتم
کامپایلر : پوران با جزوه جابری پور ، یه کم هم جاهای مهم آهو
(۰۴ شهریور ۱۳۹۱ ۰۳:۳۶ ب.ظ)f_a نوشته شده توسط: من لم تزریق رو اینجوری استدلال میکنم که یه کاری انجام بدیم که مثلا نظم رشته بدست اومده از زبان بهم بخوره...مثلا اگه تعداد a باید با b برابر باشه کاری کنیم که a<b بشه یا برعکس...یعنی با تعدادی که برای x,y,i در نظر میگیریم...اگه تونستیم برای یک مورد هم اینکارو کنیم پس زبان منظم نیست
آقای جویباری این استدلالم درسته یا نه؟
درسته؛ روش تستی و سریع به این شکله. هر رشته ای که یه مقایسه برای مقادیر نامتناهی داشته باشه منظم نیست. اگه برای یه مقدار نامتناهی هم همیشه حداقل دو مقایسه نیاز باشه مستقل از متن هم نیست. اینجور استدلال ها با حل مثال بدست میاد و سرعت حل رو خیلی زیاد میکنه. احتمال اشتباه هم هست و تضمین جوابش صددرصد نیست. بهتر بگم اینا لم تزریق نیستن. جایگزین سریعتر لم تزریقن. مثل قاعده هوپیتال توی حد.
(۰۴ شهریور ۱۳۹۱ ۰۳:۵۶ ب.ظ)آرتا نوشته شده توسط: من الان فصل اول قدسی رو تموم کردم .
خیلی کتاب جالبیه .
تا حالا با درس هایی که قبلا خوندم ، این درسها رو که مینویسم کامل خوندم
معماری : یه دور پترسون
نظریه : لینز با تمرینات
مدار منطقی : از قبل تسلط داشتم . پوران کافی بود
گسسته : گریمالدی با تمرینات . البته از قبل مطالعه داشتم
کامپایلر : پوران با جزوه جابری پور ، یه کم هم جاهای مهم آهو
خوشبحالتون...
منکه هنوز به صورت جدی شروع نکردم...از مهر به امید خدا شروع میکنم...
(۰۴ شهریور ۱۳۹۱ ۰۴:۰۷ ب.ظ)f_a نوشته شده توسط: خوشبحالتون...
منکه هنوز به صورت جدی شروع نکردم...از مهر به امید خدا شروع میکنم...
شما هم اگه یه هدف خوب واسه خودتون داشته باشید حتما موفق خواهید شد.
می گم من بعضی از این درس ها رو قبلا خوندم.
ممنون از پاسختون آقای Jooybari . لطف میکنین این سوالامم کامل توضیح بدید به ترتیب؟
این i چطور انتخاب میشه؟
مثلا برای زبان{۱ +a^ {m} b^ {m، نوشته بود |xy| نمیتونه بزرگتر از m باشه .خوب این درست.
و حریف کاری جز انتخاب y حاوی فقط a نمیتونه انجام بده!!!!! یعنی چی؟؟
حال با استفاده از i=2 رشته بدست آمده {w2= a^ {m+k} b^{m+1 میشود که در L نیست.
چرا مثلا واس i حدس زد که ۲ انتخاب بشه؟ چطوری!؟بهد که ۲ شد چرا {a^ {m+k شده
__________
ی سوال دیگه واس {a^{M}b^{M چرا y فقط شامل a میتونه باشه؟ اگه w=ab در نظر بگیریم اونوقتم y فقط شمال b هست یا واس M بزرگ شامل a هست ک گفتین ؟
مثلا aaabbb اونوقت میشه این xy رو همه aaabbb در نظر گرفت؟؟؟ x رو چی انتخاب کنیم؟ y رو چی؟
aaabb میشه x و
b مثلا y !!!
اینام میشه پس؟
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: این i چطور انتخاب میشه؟
i یک توانه. باید برای تمام حالات ممکن x و y و z بشه حداقل یک i پیدا کرد که رشته xy^{i}z جزء زبان نباشه. یعنی همیشه مثال نقض برای اثبات اینکه "هیچ حلقه ای وجود نداره" داشته باشیم. حریف ما تمام حالات شکستن رشته رو میگه. ما باید برای هرکدوم از این حالات یک توان بگیم که رشتش جزء زبان نباشه.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: مثلا برای زبان{۱ +a^ {m} b^ {m، نوشته بود |xy| نمیتونه بزرگتر از m باشه .خوب این درست.
و حریف کاری جز انتخاب y حاوی فقط a نمیتونه انجام بده!!!!! یعنی چی؟؟
M حرف اول رشتمون فقط a هست. چون فرضمون اینه که y در M حرف اول رشتست پس فقط میتونه یه تعدادی a باشه.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: حال با استفاده از i=2 رشته بدست آمده {w2= a^ {m+k} b^{m+1 میشود که در L نیست.
چرا مثلا واس i حدس زد که ۲ انتخاب بشه؟ چطوری!؟بهد که ۲ شد چرا {a^ {m+k شده
رشته اولمون xyz هست. وقتی i=2 بشه رشته جدیدمون میشه xyyz. درواقع i توان y هست. اگه برابر صفر بود رشته جدید میشد xz.
توی این مثال هر مقدار غیر از ۱ (بدیهیه که ۱ نمیتونه باشه) انتخاب کنیم جواب میده.
چرا M+k شد هم چون طول y یکبار دیگه تکرار شد. ابتدای رشته xyz تعداد Mتا a داریم. y هم kتا a داره و جزء Mتای اوله. پس اول رشته xyyz میشه M+kتا a.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: ی سوال دیگه واس {a^{M}b^{M چرا y فقط شامل a میتونه باشه؟ اگه w=ab در نظر بگیریم اونوقتم y فقط شمال (
مقدار M بزرگ فرض شده. بزرگتر از تعداد حالات ماشینمون. شما M رو ۱ فرض کردید. فرض قضیه رو نقض کردید.
(۰۴ شهریور ۱۳۹۱ ۰۵:۲۶ ب.ظ)skygirl_00 نوشته شده توسط: مثلا aaabbb اونوقت میشه این xy رو همه aaabbb در نظر گرفت؟؟؟ x رو چی انتخاب کنیم؟ y رو چی؟
aaabb میشه x و
b مثلا y !!!
اینام میشه پس؟
رشتمون {a^{M}b^{M هست. تعداد حالت ماشینمون باید حداکثر M-1 باشه. درضمن xy کوچکتر مساویه M هست. اصلاً دنبال مثال به این شکل نباشید.
(۰۳ شهریور ۱۳۹۱ ۰۶:۲۲ ب.ظ)skygirl_00 نوشته شده توسط: خوب شماهایی ک تو نظریه دستی دارین بگین من لینز و کتاب حل تمریناشو (برای تست کردن راه حل )داشته باشم خوبه یا کتاب ابراهیم اکبری رو بگبرم بخونم؟
به نظر من هردوش
کتاب اکبری تمرین زیاد حل کرده برای تمرین کتاب خوبیه
لینزهم که باید حتما خونده بشه و تمرینهاش حل بشه
بعد اونوقت کتاب تستو کنکورم باید داشته باشم ؟ وقتی اکبری رو هم خریدم؟لازم میشه؟
(۰۴ شهریور ۱۳۹۱ ۰۲:۱۵ ب.ظ)shima_24 نوشته شده توسط: هوش به نظرتون راهیان خوبه بگیرم یا نه؟ از هوش پوران خوشم نمیاد.
راهیان میگن خوبه من اول از رو پارسه خوندم به نظرم پراکنده میگفت البته voiceش خیلی عالیه الان دارم از رو مقسمی میخونم خیلی راحت گفته واسه شروع خوبه ولی در نهایت راسل باید خونده شه اگه راهیان رو خوندی نتیجه گرفتی به ما هم بگو