سلام خسته نباشید
ببخشید دوستان کسی میتونه استفاده از لم تزریق رو برای من توضیح بده؟؟
میخوام از لم تزریق برای اثبات مستقل از متن نبودن زبان استفاده کنم
اما فکر کنم دارم اشتباه میفهممش چون چند بار خوندمش ولی باهاش میتونم ثابت کنم مثلا a^n b^n مستقل از متن نیستش
خواهش میکنم اگر خوب بلدید برام توضیح بدید چون برای مستقل از متن نبودن پسته خیلی راه مطمینی نیست چون شاید به ذهنمون سر جلسه نرسه چه جور فلان زبان رو با پشته پیاده سازی کنیم و در نتیجه تو کنکور بزنیم مستقل از متن نیست و غلط از اب دراد
با تشکر ویژه از کسانی که وقت میگذارند و راهنمایی میکنند
ببینید مثلا برای زبان w1w2 که *)w=)a+b( و اندازه w1 و w2 برابر باشن و همچنین w1=w2 باشه
اصلا نمیدونم همون اول کل رشتم رو چی بگیرم که بتونم از طریق لم تزریق حلش کنم
ممنون میشم اگر راهنمایی کنید
واسه زبان [tex]a^nb^n[/tex] با لم پمپ یه هیج عنوان نمیشه ثابت کرد که مستقل از متن نیست.
لم تزریق برای اثبات مستقل از متن نبودن زبان ها کاربرد داره مثلا زبان [tex]a^nb^nc^n[/tex] اگه v رو از aها و y رو از bها در نظر بگیرید، اگه تزریق کنیم مثلا میرسیم به رشته aaabbbc که دیگه جزو زبان نیست پس مستقل از متن نیست.
برای زبان [tex]a^nb^n[/tex] اگه طبق الگوریتم رقیب که توی بعضی کتابها اومده شما اول v رو از a بگیرید، میشه y رو از bها بگیریم اونوقت به تعداد افزایش a ، کاراکتر bهم افزایش می یابد مثلا ab میشه aabb یا aaabbb و الی آخر . که همه رشته های تولید شده جزو زبان هستند.
(۲۶ دى ۱۳۹۳ ۱۲:۰۰ ق.ظ)ma3070 نوشته شده توسط: ببینید مثلا برای زبان w1w2 که *)w=)a+b( و اندازه w1 و w2 برابر باشن و همچنین w1=w2 باشهبرای این زبان خاص هم کافیه که v رو از w1 و قسمت a انتخاب کنید ، سپس اگر y از w1 و قسمت b انتخاب بشه، با تزریق رشته های به دست آمده جزو زبان نخواهند بود.
اصلا نمیدونم همون اول کل رشتم رو چی بگیرم که بتونم از طریق لم تزریق حلش کنم
ممنون میشم اگر راهنمایی کنید
مثلا w1= ab و طبیعتا w2=ab یعنی رشته abab از داخل زبان انتخاب شده.
حالا ما فرض کنیم v=a و y=b که از بخش w1 جدا شدند.
در تزریق باید v و y را پمپ کنیم مثلا w1 میشه aabb ولی w2 همون ab باقی مونده و یعنی رشته ما اینه : aabbab که طبیعتا جزو زبان نیست پس این زبان مستقل از متن نیست.
(۲۶ دى ۱۳۹۳ ۱۲:۱۹ ق.ظ)ana9940 نوشته شده توسط: واسه زبان [tex]a^nb^n[/tex] با لم پمپ یه هیج عنوان نمیشه ثابت کرد که مستقل از متن نیست.
لم تزریق برای اثبات مستقل از متن نبودن زبان ها کاربرد داره مثلا زبان [tex]a^nb^nc^n[/tex] اگه v رو از aها و y رو از bها در نظر بگیرید، اگه تزریق کنیم مثلا میرسیم به رشته aaabbbc که دیگه جزو زبان نیست پس مستقل از متن نیست.
برای زبان [tex]a^nb^n[/tex] اگه طبق الگوریتم رقیب که توی بعضی کتابها اومده شما اول v رو از a بگیرید، میشه y رو از bها بگیریم اونوقت به تعداد افزایش a ، کاراکتر bهم افزایش می یابد مثلا ab میشه aabb یا aaabbb و الی آخر . که همه رشته های تولید شده جزو زبان هستند.
(۲۶ دى ۱۳۹۳ ۱۲:۰۰ ق.ظ)ma3070 نوشته شده توسط: ببینید مثلا برای زبان w1w2 که *)w=)a+b( و اندازه w1 و w2 برابر باشن و همچنین w1=w2 باشهبرای این زبان خاص هم کافیه که v رو از w1 و قسمت a انتخاب کنید ، سپس اگر y از w1 و قسمت b انتخاب بشه، با تزریق رشته های به دست آمده جزو زبان نخواهند بود.
اصلا نمیدونم همون اول کل رشتم رو چی بگیرم که بتونم از طریق لم تزریق حلش کنم
ممنون میشم اگر راهنمایی کنید
مثلا w1= ab و طبیعتا w2=ab یعنی رشته abab از داخل زبان انتخاب شده.
حالا ما فرض کنیم v=a و y=b که از بخش w1 جدا شدند.
در تزریق باید v و y را پمپ کنیم مثلا w1 میشه aabb ولی w2 همون ab باقی مونده و یعنی رشته ما اینه : aabbab که طبیعتا جزو زبان نیست پس این زبان مستقل از متن نیست.
ممنون از پاسختون خیلی لطف کردید موفق باشید