سلام چطوری زبا منظم رو از مستقل از متن تشخیص بدم؟
چطور بفهمم سوالم تکراری نیست که مطرحش نکنم؟
سلام. زبان منظم زبانیه که بشه با یه ماشین متناهی یا گرامر منظم یا عبارت منظم تعریفش کرد. با لم تزریق میشه مشخص کرد که زبان منظمه یا نه.
مشکل من اینه که هر چی از روی کتابا میخونم از لم تزریق سردر نمیارم؟؟؟میشه یادم بدین لم تزریقو؟؟؟
امیدوارم توضیحاتمو متوجه بشید
(۰۵ مهر ۱۳۹۳ ۱۱:۱۹ ب.ظ)fatemeh69 نوشته شده توسط: امیدوارم توضیحاتمو متوجه بشیدمن فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.
(۰۷ مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط: من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.
خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد
(۰۷ مهر ۱۳۹۳ ۰۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:(07 مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط: من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.
خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد
مثال نقض دارید ؟
(۰۷ مهر ۱۳۹۳ ۱۱:۳۴ ب.ظ)Pakniat نوشته شده توسط:(07 مهر ۱۳۹۳ ۰۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:(07 مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط: من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.
خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد
مثال نقض دارید ؟
برای چی مثال نقض دارم یا نه؟
من می گم لم تزریق زبان های منظم اصولا به هدف اثبات نامنظمی زبان های نامنظم طراحی شده و کاربرد دیگری ندارد
شما می گید خیر می شه باهاش مستقل از متن نبودن رو هم تشخیص داد
اگر حرفتون درسته براش مثال بیارید مثلا یه زبان مستقل از متن [tex]L=\{a^nb^n,\: n>=0\: \}[/tex] رو بدیم به لم تزریق واسمون اثبات می کنه که نامنظمه و اگر زبان غیر مستقل از متن [tex]L=\{a^nb^nc^n,\: n>=0\: \}[/tex] رو هم به لم تزریق بدهیم باز برامون ثابت می کنه که اینزبان نامنظمه و واسه لم تزریق روند کار روی این دو زبان یکسانه و واسش مهم نیست که زبان نامنظم ما آیا مستقل از متن هم هیت یا خیر مهم اینه که نامنظمه.
نمی دونم فرضیه ذهنی شما چیه و چه دلیلایی واسش دارید اگه دلایلتونو بنویسید و با چند مثال بیان کنید بیشتر متوجه منظورتون می شم
(۰۸ مهر ۱۳۹۳ ۰۱:۳۴ ق.ظ)fatemeh69 نوشته شده توسط:(07 مهر ۱۳۹۳ ۱۱:۳۴ ب.ظ)Pakniat نوشته شده توسط:(07 مهر ۱۳۹۳ ۰۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:(07 مهر ۱۳۹۳ ۱۲:۵۴ ق.ظ)Pakniat نوشته شده توسط: من فکر میکنم با لم تزریق زبان منظم میشه مستقل از متن نبودن زبان ها رو تشخیص داد ، می خواستم نظرتون رو در این مورد بدونم.
خیر این طور نیست با لم تزریق ویژه زبان های منظم تنها و تنها و تنها می توان نامنظم بودن یک زبانی را اثبات کرد
مثال نقض دارید ؟
برای چی مثال نقض دارم یا نه؟
من می گم لم تزریق زبان های منظم اصولا به هدف اثبات نامنظمی زبان های نامنظم طراحی شده و کاربرد دیگری ندارد
شما می گید خیر می شه باهاش مستقل از متن نبودن رو هم تشخیص داد
اگر حرفتون درسته براش مثال بیارید مثلا یه زبان مستقل از متن [tex]L=\{a^nb^n,\: n>=0\: \}[/tex] رو بدیم به لم تزریق واسمون اثبات می کنه که نامنظمه و اگر زبان غیر مستقل از متن [tex]L=\{a^nb^nc^n,\: n>=0\: \}[/tex] رو هم به لم تزریق بدهیم باز برامون ثابت می کنه که اینزبان نامنظمه و واسه لم تزریق روند کار روی این دو زبان یکسانه و واسش مهم نیست که زبان نامنظم ما آیا مستقل از متن هم هیت یا خیر مهم اینه که نامنظمه.
نمی دونم فرضیه ذهنی شما چیه و چه دلیلایی واسش دارید اگه دلایلتونو بنویسید و با چند مثال بیان کنید بیشتر متوجه منظورتون می شم
من فکر می کنم لم pumping ابزاری است که برای اثبات : نامنظم بودن ، مستقل از متن بودن و غیر خطی بودن میشه استفاده کرد ، در زبان های نامنظم به صورت dfa و در مستقل از متن بودن به صورت گرامر مستقل از متن بیان میشه ، مثلا [tex]w.w^R[/tex]رو می تونید اثبات کنید نامنظمه ، اما مستقل از متن هست چون براش گرامر داریم اما [tex]a^nb^nc^n[/tex] رو با همون لم تزریق زبان نامنظم میشه اثبات کرد مستقل از متن نیست چون براش نه گرامر و نه pda داریم اما با یک i میشه خارج کرد.
در مجموع به دنبال دلیلی برای قوی تر بودن لم مستقل از متن نسبت به نامنظم می گردم و فکر می کنم لم مستقل از متن بیان دیگه ای از لم نامنظم هست !
(۱۰ مهر ۱۳۹۳ ۰۱:۰۱ ق.ظ)Pakniat نوشته شده توسط: من فکر می کنم لم pumping ابزاری است که برای اثبات : نامنظم بودن ، مستقل از متن بودن و غیر خطی بودن میشه استفاده کرد ، در زبان های نامنظم به صورت dfa و در مستقل از متن بودن به صورت گرامر مستقل از متن بیان میشه ، مثلا [tex]w.w^R[/tex]رو می تونید اثبات کنید نامنظمه ، اما مستقل از متن هست چون براش گرامر داریم اما [tex]a^nb^nc^n[/tex] رو با همون لم تزریق زبان نامنظم میشه اثبات کرد مستقل از متن نیست چون براش نه گرامر و نه pda داریم اما با یک i میشه خارج کرد.
در مجموع به دنبال دلیلی برای قوی تر بودن لم مستقل از متن نسبت به نامنظم می گردم و فکر می کنم لم مستقل از متن بیان دیگه ای از لم نامنظم هست !
من فکر می کنم شما چند مفهوم رو باهم مخلوط کرده اید
این مطالب رو می گم صرفا برای این که پایه های ذهنی م رو بیان کنم
اولا ما سه لم تزریق داریم لم تزریق ویژه زبان های منظم - لم تزریق ویژه زبان های مستقل از متن- لم تزرریق ویژه زبان های خطی
نظریه درسی با پایخه ی ریاضی است یعنی اگر جدا از کنکور به آن نگاه کنیم هر چیزی را باید اثبات کرد
گاهی ما می گوییم فلان منظم است به ما می گویند این حرفت را اثبات کن ما فورا برای آن زبان dfa می کشیم یا گرامر منظم می دهیم یا با عبارت منظم بیان می کنیم می گوییم بفرما این هم اثباتش
گاهی ما می گوییم فلان زبان نامنظم است می گویند اثبات کن ما می گوییم خب هیچ dfa ای برای آن وجود ندارد
می گویند:از کجا معلوم؟! شاید برای آن dfa ای باشد اما تو نتواسته ای پیدا کنی اثبات کن که هیچ dfa ای برای آن وجود ندارد
این جاست که لم تزریق به کار ما می آۀید
یعنی لم تزریق زبان های منظم اثباتی ریاضی محور برای نامنظم بودن یک زبان نامنظم است
و لم تزریق زبان های مستقل از متنی اثباتی برای مستقل از متن نبودن یک زبان غیر مستقل از متن است
و لم تزریق مخصوص زبان های خطی اثباتی برای غیر خطی بودن یک زبان غیر خطی است.
حالا طبق طبقه بندی چامسکی کوچکترین مجموعه زبان ها منظم هیتند و که زیر مجموعه ی مجوعه ی بزرگتری به نام زبان های مستقل از متن هستند و آن ها زیر مجموعه ی مجوعه ی بزرگتری یعنی زبان های حساس به متن هستند که خود زیر مجوعه ی مجوعه ی بزرگتری به نام زبان های نوع صفر (r.e) هستند.
خب این یعنی اگر با لم تزریق اثبات کردیم که زبانی منظم نیست پس این زبان خارج از مجوعه ی زبان های منظم قرار می گیرید (و معلوم نیست که در مجموعه ی مستقل از متن باشد یا حساس به متن یا نوع صفر یا حتی خارج از آن.
پس زبانی که خارج از مجموعه ی منظم است معلوم نیست که آیا مستقل از متن هست یا نه
لم تزریق مخصوص زبان های منظم ، نامنظم بودن یک زبان منظم را اثبات می کند (یعنی اثبات می کند برای این زبان هیچ dfa یا گرامر منظم یا عبارت منظمی وجود ندارد) پس عضو مجموعه ی زبان های منظم نیست حالا این که عضو کدام مجوعه است معلوم نیست.
برای اثبات منظم بودن از dfa- گرامرمنظم یا عبارت منظم استفاده می کنیم
برای اثبات غیر منظم بودن از لم تزریق مخصوص زبان های منظم استفاده می کنیم
برای اثبات مستقل از متن بودن یک زبان از pda- گرامر مستقل از متن استفاده می کنیم
برای اثبات مستقل از متن نبودن از لم تزریق زبان های مستقل از متن استفاده می کنیم
برای اثبات خطی بودن زبانی از گرامر خطی استفاده می کنیم
برای اثبات غیر خطی بودن زبانی از لم تزری۴ق مخصوص زبان های غیر خطی استفاده می کنیم
هر ابزاری را بهر کاری ساخته اند!