سلام دوستان ،
ممکنه یه توضیح بدین که چه جوری می شه از قضیه لمِ تزریق برا تشخیصِ نامنظم بودنِ زبان ها استفاده کرد؟؟
چون متاسفانه من سرِ کلاسِِ درسِ نظریه نبودم و واقعا این جا به مشکل بر خوردم !
پیشاپیش ممنــــــون
سلام. ببینید این مطالب بدردتون میخوره:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یه توضیح کوچیک بدم برای اینه چون زبان های منظم با تعداد حالات محدود dfa قابل پیاده سازین؛ اگه زبانمون رشته های با طول بیشتر از تعداد حالات رو قبول کنه پس حتماً از یکی از حالات حداقل دوبار عبور کرده. پس حلقه ای توی dfa داره. نشون میدیم یه رشته خاص توی زبانمون وجود داره که هرجاش حلقه بخوره باز هم رشته های اشتباهی تولید میکنه. (چون حافظه نامحدود نداره، نمیتونه تعداد دفعات تکرار حلقه رو بشمره.)
ممنون آره مفید بود ...
ولی راهِ سریع تری برا تشخیصِ نا منظم بودن زبان نیست،چون به نظرم این راهِ وقت گیره!!
هر زبانی که بشه با عبارت منظم نوشت منظمه. هر زبانی که به حافظه نامحدود نیاز داشته باشه منظم نیست. مثلاً برابری تعداد a ها با b ها. توجه کنید توی حافظه محدود ماشین ها و زبانهای منظم مشکل ندارن. مثلاً باقی مانده نسبت به عدد 1000 و یا رشته های حداکثر با طول 1000 و .... توی سوالات یکم زبانو میپیچونن و شما تا میتونید باید بفرم ساده بنویسید. پیشنهاد میکنم لم تزریق رو برای چندتا زبان بنویسید تا فرم رشته هایی که منظم نیستن دستتون بیاد. بعدش بندرت به این لم نیاز خواهید داشت.
برای تشخیص زبان های منظم چند روش وجود داره ، 1-عبارات منظم 2-ماشین متناهی FSA و 3-گرامر منظم
برای اثبات منظم نبودن بایستی از روش های اثباتی من لم تزریق استفاده کرد. کلا با تمرین زیاد میشه منظم بودن یا نبودن زبان رو مشخص کرد اما برای زبان های پیچیده حتما باید یه روش درست و علمی مثل لم تزریق استفاده کرد.
یه جورایی سعی کن از 3 روش های بالا ببین می تونی مشخص کنی زبان منظمه یا نه ، اگه نشد منظم نیست ، البته کلی میگم و همیشه درست نیست چون بستگی به مهارت و تجربه افراد داره. اما خیلی زبان های کمی وجود داره که حتما باید از لم تزریق رفت . درک منظم بودن با ماشین متناهی خیلی راحت تر از همشونه. ببین بایه ماشین متناهی میتونی زبان رو پیاده سازی کنی یا نه. لم تزریق هم همین مطلب رو میگه، که طول رشته محدود باشه یا بتوان رشته هایی با اندازه مشخص رو بین دو رشته با طول ثابت تزریق کرد(همون متغیر اندیس بالا در فرمول لم تزریق). در چند تا نکته رو به یاد داشته باش:
1-زبان های متناهی منظم هستند.
2- زبانهایی که فقط یه رشته تکرار میشه(هر رشته ای) منظم هستند.
3-زبانهایی که توشون شمارش در کار نباشه منظم هستند.
4- بیشتر مواقع وقتی بین رشت هایی تکرار شونده یه رشته ثابت باشه و بین این شته ای فرمول ریاضی باشه زبان منظم نیست چون برای پیدا کردن فرمول نیاز به حافظه هست که ماشین متناهی نداره
خیلی کلی بودن و فقط جهت دقت به برخی نکات بود. تمرین رو بیشتر از هر چیزی من یکی توصیه می کنم