۰
subtitle
ارسال: #۱
  
قضیه لمِ تزریق
سلام دوستان ،
ممکنه یه توضیح بدین که چه جوری می شه از قضیه لمِ تزریق برا تشخیصِ نامنظم بودنِ زبان ها استفاده کرد؟؟
چون متاسفانه من سرِ کلاسِِ درسِ نظریه نبودم و واقعا این جا به مشکل بر خوردم !
پیشاپیش ممنــــــون
ممکنه یه توضیح بدین که چه جوری می شه از قضیه لمِ تزریق برا تشخیصِ نامنظم بودنِ زبان ها استفاده کرد؟؟
چون متاسفانه من سرِ کلاسِِ درسِ نظریه نبودم و واقعا این جا به مشکل بر خوردم !
پیشاپیش ممنــــــون
۴
ارسال: #۲
  
قضیه لمِ تزریق
سلام. ببینید این مطالب بدردتون میخوره:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
یه توضیح کوچیک بدم برای اینه چون زبان های منظم با تعداد حالات محدود dfa قابل پیاده سازین؛ اگه زبانمون رشته های با طول بیشتر از تعداد حالات رو قبول کنه پس حتماً از یکی از حالات حداقل دوبار عبور کرده. پس حلقه ای توی dfa داره. نشون میدیم یه رشته خاص توی زبانمون وجود داره که هرجاش حلقه بخوره باز هم رشته های اشتباهی تولید میکنه. (چون حافظه نامحدود نداره، نمیتونه تعداد دفعات تکرار حلقه رو بشمره.)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
یه توضیح کوچیک بدم برای اینه چون زبان های منظم با تعداد حالات محدود dfa قابل پیاده سازین؛ اگه زبانمون رشته های با طول بیشتر از تعداد حالات رو قبول کنه پس حتماً از یکی از حالات حداقل دوبار عبور کرده. پس حلقه ای توی dfa داره. نشون میدیم یه رشته خاص توی زبانمون وجود داره که هرجاش حلقه بخوره باز هم رشته های اشتباهی تولید میکنه. (چون حافظه نامحدود نداره، نمیتونه تعداد دفعات تکرار حلقه رو بشمره.)
۳
ارسال: #۳
  
قضیه لمِ تزریق
هر زبانی که بشه با عبارت منظم نوشت منظمه. هر زبانی که به حافظه نامحدود نیاز داشته باشه منظم نیست. مثلاً برابری تعداد a ها با b ها. توجه کنید توی حافظه محدود ماشین ها و زبانهای منظم مشکل ندارن. مثلاً باقی مانده نسبت به عدد ۱۰۰۰ و یا رشته های حداکثر با طول ۱۰۰۰ و .... توی سوالات یکم زبانو میپیچونن و شما تا میتونید باید بفرم ساده بنویسید. پیشنهاد میکنم لم تزریق رو برای چندتا زبان بنویسید تا فرم رشته هایی که منظم نیستن دستتون بیاد. بعدش بندرت به این لم نیاز خواهید داشت.
۳
ارسال: #۴
  
قضیه لمِ تزریق
برای تشخیص زبان های منظم چند روش وجود داره ، ۱-عبارات منظم ۲-ماشین متناهی FSA و ۳-گرامر منظم
برای اثبات منظم نبودن بایستی از روش های اثباتی من لم تزریق استفاده کرد. کلا با تمرین زیاد میشه منظم بودن یا نبودن زبان رو مشخص کرد اما برای زبان های پیچیده حتما باید یه روش درست و علمی مثل لم تزریق استفاده کرد.
یه جورایی سعی کن از ۳ روش های بالا ببین می تونی مشخص کنی زبان منظمه یا نه ، اگه نشد منظم نیست ، البته کلی میگم و همیشه درست نیست چون بستگی به مهارت و تجربه افراد داره. اما خیلی زبان های کمی وجود داره که حتما باید از لم تزریق رفت . درک منظم بودن با ماشین متناهی خیلی راحت تر از همشونه. ببین بایه ماشین متناهی میتونی زبان رو پیاده سازی کنی یا نه. لم تزریق هم همین مطلب رو میگه، که طول رشته محدود باشه یا بتوان رشته هایی با اندازه مشخص رو بین دو رشته با طول ثابت تزریق کرد(همون متغیر اندیس بالا در فرمول لم تزریق). در چند تا نکته رو به یاد داشته باش:
۱-زبان های متناهی منظم هستند.
۲- زبانهایی که فقط یه رشته تکرار میشه(هر رشته ای) منظم هستند.
۳-زبانهایی که توشون شمارش در کار نباشه منظم هستند.
۴- بیشتر مواقع وقتی بین رشت هایی تکرار شونده یه رشته ثابت باشه و بین این شته ای فرمول ریاضی باشه زبان منظم نیست چون برای پیدا کردن فرمول نیاز به حافظه هست که ماشین متناهی نداره
خیلی کلی بودن و فقط جهت دقت به برخی نکات بود. تمرین رو بیشتر از هر چیزی من یکی توصیه می کنم
برای اثبات منظم نبودن بایستی از روش های اثباتی من لم تزریق استفاده کرد. کلا با تمرین زیاد میشه منظم بودن یا نبودن زبان رو مشخص کرد اما برای زبان های پیچیده حتما باید یه روش درست و علمی مثل لم تزریق استفاده کرد.
یه جورایی سعی کن از ۳ روش های بالا ببین می تونی مشخص کنی زبان منظمه یا نه ، اگه نشد منظم نیست ، البته کلی میگم و همیشه درست نیست چون بستگی به مهارت و تجربه افراد داره. اما خیلی زبان های کمی وجود داره که حتما باید از لم تزریق رفت . درک منظم بودن با ماشین متناهی خیلی راحت تر از همشونه. ببین بایه ماشین متناهی میتونی زبان رو پیاده سازی کنی یا نه. لم تزریق هم همین مطلب رو میگه، که طول رشته محدود باشه یا بتوان رشته هایی با اندازه مشخص رو بین دو رشته با طول ثابت تزریق کرد(همون متغیر اندیس بالا در فرمول لم تزریق). در چند تا نکته رو به یاد داشته باش:
۱-زبان های متناهی منظم هستند.
۲- زبانهایی که فقط یه رشته تکرار میشه(هر رشته ای) منظم هستند.
۳-زبانهایی که توشون شمارش در کار نباشه منظم هستند.
۴- بیشتر مواقع وقتی بین رشت هایی تکرار شونده یه رشته ثابت باشه و بین این شته ای فرمول ریاضی باشه زبان منظم نیست چون برای پیدا کردن فرمول نیاز به حافظه هست که ماشین متناهی نداره
خیلی کلی بودن و فقط جهت دقت به برخی نکات بود. تمرین رو بیشتر از هر چیزی من یکی توصیه می کنم
۰
ارسال: #۵
  
قضیه لمِ تزریق
ممنون آره مفید بود ...
ولی راهِ سریع تری برا تشخیصِ نا منظم بودن زبان نیست،چون به نظرم این راهِ وقت گیره!!
ولی راهِ سریع تری برا تشخیصِ نا منظم بودن زبان نیست،چون به نظرم این راهِ وقت گیره!!
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سوال از قضیه ی بیز | Nazari76 | ۱ | ۳,۱۸۷ |
۲۶ خرداد ۱۳۹۷ ۰۷:۵۴ ب.ظ آخرین ارسال: saeed_vahidi |
|
تشخیص دو قضیه از هم | Mr.R3ZA | ۵ | ۵,۶۴۸ |
۳۱ اردیبهشت ۱۳۹۷ ۱۲:۱۴ ق.ظ آخرین ارسال: pioneer01 |
|
توضیح قضیه گرچ گودین | یه نفر | ۰ | ۱,۴۸۸ |
۲۰ فروردین ۱۳۹۶ ۱۲:۵۵ ب.ظ آخرین ارسال: یه نفر |
|
قضیه یا فرمول حداکثر تعداد دستورات دو آدرسی / یک آدرسی | mmm1374 | ۲ | ۲,۳۹۹ |
۰۳ بهمن ۱۳۹۵ ۰۲:۰۰ ب.ظ آخرین ارسال: Saman |
|
مثال های قضیه ی فرما | Hopegod | ۲ | ۲,۸۴۹ |
۲۱ آذر ۱۳۹۵ ۰۱:۰۶ ق.ظ آخرین ارسال: Hopegod |
|
لم تزریق زبان خطی | teacherpc | ۴ | ۴,۳۶۰ |
۰۳ بهمن ۱۳۹۴ ۰۷:۵۳ ب.ظ آخرین ارسال: Jooybari |
|
حل از طریق قضیه ی Master | H-Arshad | ۵ | ۵,۶۸۱ |
۲۱ آبان ۱۳۹۴ ۰۳:۲۰ ق.ظ آخرین ارسال: Azar.099 |
|
چند سوال در رابطه به لم تزریق خانواده زبان های منظم | joyebright | ۵ | ۶,۱۳۶ |
۲۰ آبان ۱۳۹۴ ۰۲:۰۵ ب.ظ آخرین ارسال: Jooybari |
|
قضیه بیز چیست؟؟؟ | saberz | ۵ | ۷,۸۰۰ |
۱۸ آبان ۱۳۹۴ ۰۹:۵۷ ب.ظ آخرین ارسال: saberz |
|
فصل خطاها- اثبات قضیه | Pure Liveliness | ۲ | ۲,۹۴۷ |
۲۹ تیر ۱۳۹۴ ۰۳:۰۴ ب.ظ آخرین ارسال: Pure Liveliness |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close