لینز رو هم میخونم متوجه نمیشم......چی کار کنم این لم تزریق رو بفهمم؟؟ مثال هاشو هم میخونم متوجه نمیشم
لم تزریق برای زبان مستقل از متن رو بیشتر متوجه نمیشم
جزوه ای کتابی چیزی سراغ دارید که از روش بخونم بهتر بفهمم؟؟
منم مثل شما شدیدا با لم تزریق مشکل داشتم
اینقدر تو مانشت و نت جستجو کردم و جزوه های مختلف رو خوندم تا یادش گرفتم
شمام همین کارو بکنبد تو همین مانشت یادمه چندنفر خوب توضیح داده بودن از هر کدوم یه تیکه بفهمبد واخر جمع بندی کنید.
ممنون از راهنماییتون.......
کلا این مبحث چه قدر مهمه؟؟ سالای پیش چه تعداد سوال ازش اومده؟؟
کلا از فصل آتاماتا به بعد توی فهمیدن بعضی مباحث مشکل دارم....البته هنوز تورینگ و بعدش رو نخوندم نمیدونم اونا چه طوریه......
البته از قبلش هم لم تزریق برای زبان منظم رو مشکل داشتم.....توی دانشگاه واسه ما لم تزریق رو حذف کرده بودن
(۳۰ شهریور ۱۳۹۲ ۰۱:۵۲ ب.ظ)Fardad-A نوشته شده توسط: یه جورایی خیلی شبیه اصل لانه کبوتری تو آماره. یه ویژگی زبان منظم را میگه و شما برای اثبات نامنظم بودن یه زبان،فرض میکنید منظمه ،بعد مثالی پیدا میکنید که فاقد اون ویژگی است. پیدا کردن مثال اگه زبان عجیب غریب باشه کمی خلاقیت می طلبد.منظورت برهان خلفه؟
منم مشکل دارم البته تو لینز هنوز به اینجاش نرسیدم ولی قبلا نتونسته بودم بفهممش
کلا لم که می شنیدم قاطی می کردم
(۳۱ شهریور ۱۳۹۲ ۱۲:۱۹ ق.ظ)farham_heidari نوشته شده توسط: سلام دوستان داستان لم تزریق از این قراره
اول من برای زبان های منظم توضیح میدم
شما قبول دارید اگر زبانی منظم باشه یک dfa دارد ؟؟
خوب هر dfa یه تعداد حالت داره درسته ؟ مثلا m تا حالت .. تا اینجا حله ؟
اگر زبانی منظم نامتنهای باشه یعنی چی ؟ یعنی این که رشته هایی داره با طول های خیلی بزرگ قبول ؟
حالا یه زبان منظم نامتنهای را در نظر بگیرید . یه dfa دارد با m حالت حالا اگر یه رشته بزرگتر از m توی این dfa وارد بشه چی میشه ؟؟
یه جایی وجود داره که دور اتفاق میفته حله ؟؟
با لم تزریق اون دور را پیدا میکنیم و به توان میرسونیم باید به هر توانی رسید باز هم رشته جز زبان باشه حله ؟؟
تا اینجا حوصلم شد
ممنون.....درمورد مستقل از متن هم اگه میشه توضیح بدید.....خیلی خوبه......ممنون..
(۳۱ شهریور ۱۳۹۲ ۱۲:۱۹ ق.ظ)farham_heidari نوشته شده توسط: سلام دوستان داستان لم تزریق از این قراره
اول من برای زبان های منظم توضیح میدم
شما قبول دارید اگر زبانی منظم باشه یک dfa دارد ؟؟
خوب هر dfa یه تعداد حالت داره درسته ؟ مثلا m تا حالت .. تا اینجا حله ؟
اگر زبانی منظم نامتنهای باشه یعنی چی ؟ یعنی این که رشته هایی داره با طول های خیلی بزرگ قبول ؟
حالا یه زبان منظم نامتنهای را در نظر بگیرید . یه dfa دارد با m حالت حالا اگر یه رشته بزرگتر از m توی این dfa وارد بشه چی میشه ؟؟
یه جایی وجود داره که دور اتفاق میفته حله ؟؟
با لم تزریق اون دور را پیدا میکنیم و به توان میرسونیم باید به هر توانی رسید باز هم رشته جز زبان باشه حله ؟؟
تا اینجا حوصلم شد
با تشکر از صحبت های دوستمون. یه مواردی هم باید ذکر بشه. رشته ی انتخاب شده با طول بزرگتر از m را در تمام حالات ممکن به فرم w=xyz میشکونیم که اندازه y بزگتر مساوی ۱ و مجموع اندازه x و y کوچکتر مساوی m باشه. دلیل: y همون دور انتخابی در nfa هست. چون اندازه nfa رو m فرض کردیم این دور باید در m حرف اول رشته انتخابیمون حداقل ۱ بار تکرار بشه. دلیل اون دو شرط برای y و xy همینه. چون ماشین متناهی قابلیت شمارش دور رو نداره پس باید تمام رشته های بفرم [tex]w^'=xy^iz[tex] هم جزء زبان باشه.
برای سادگی میتونید این لم رو بصورت بازی درنظر بگیرید. هدف شما از بازی اثبات نامنظم بودن زبانه. این بازی ۴ مرحله داره:
۱- حریفتون یک زبان مشخص میکنه.
۲- شما یک رشته که طولش تابعی از m (اندازه فرضی nfa ماشین) باشه و از m بزرگتر باشه (تا مطمئن بشیم دور داره) رو مشخص میکنید.
۳- حریف این رشته رو به تمام حالات ممکن به فرم w=xyz با دو شرط اندازه y بزگتر مساوی ۱ و اندازه xy کوچکتر مساوی m میشکنه.
۴- شما برای هر حالت شکستن رشته باید یک توان برای y پیدا کنید که رشته جدید [tex]w^'=xy^iz[tex] عضو زبان نباشه.
برای لم دوم یکم کار پیچیده تر میشه. شرط شکستن رشته برای رشته w=uvxyz بصورت اندازه vy بزرگتر مساوی ۱ و اندازه vxy کوچکتر مساوی m تغییر میکنه. پیچیدگیش برای اینه که معمولاً تعداد حالات شکستن رشته زیاده میشه.
از دوستانی که کمک کردند ممنون........تازه دارم میفهمم چی به چیه
خواهشا اگه میشه بازم توضیح بدید...