ببینید مثلا برای زبان 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 که طبیعتا جزو زبان نیست پس این زبان مستقل از متن نیست.

ممنون از پاسختون خیلی لطف کردید موفق باشید