سلام دوستان عزیزم
[tex]L=\left \{ ww | w\epsilon\left \{ a,b \right \}^{*} \right \}[/tex]
این زبان مستقل از متن نیست اثبات عدم مستقلال متنی این زبان با فرض
[tex]w=a^{m}b^{m}a^{m}b^{m}[/tex]
چه طوری میشه؟
تو لینز خلاصه گفته میشه لطف کنین توضیح بدین؟
سلام. اگه درنظر بگیری a^mb^ma^mb^m=uvxyz که اندازه vy و vxy توی حوزه تعریفشون باشن، تمام حالاتی که برای vy پیش میاد به شکلهای زیره:
v,y هردم از یک حرف انتخاب بشن (v,y هردو از یکی از ۴ محدوده با تکرار m انتخاب شده باشن): طبیعتاً اگه i=2 درنظر بگیریم تعداد تکرار اون حرف بیشتر از m میشه و با طوف دومش برابر نیست. (چون بینشون یه حرف دیگه به تعداد m بار اومده نمیتونیم دو طرف a یا دوطرف b رو باهم اضافه کنیم.)
v,y از دو حرف مجاور انتخاب بشن(در حالت کلی uv=a^pb^q یا vy=b^pu^q): با انتخاب i=2 یا ترتیب رشته در یک سمت بهم میخوره (مثلاً v=abb) و یا حالتی مشابه حالت اولی برای حراقل یکی از حروف پیش میاد.
یکی از دوستان ج رو خصوصی دادن منتهی من پاسخ رو میزارم واسه همه
کافیه رشته رو طوری تجزیه کنیم که تزریق منجر به تولید رشته ای خارج زبان بشه
ماvxy را بطول کمتر از m از وسط رشته انتخاب میکنیم بعد vو y رو تزریق میکنیم که منجر میشه که رشته ای خارج زبان تولید بشه
مرسی از دوستانی که کمک میکنن خدا خیرشون بده
درسته؟
سلام
همون uvxyzای که کتاب در نظر بگیرید حالا با تکرار v وy به تعداد i فقط یک سمت تعداد a و b ها اضافه میشه و در نتیجه رشته ی مورد نظر در زبان نیست این حالت یکی از بدترین حالتهایی هست که حریف میتونه انتخاب کنه حالت دیگه هم میتونه به صورت زیر باشه
اگه vxy شما یک نوع سمبل باشن(یعنی یا a باشن یا b) با توجه به محدودیت هایی نظیر(طول vxy کمتر از m)همیشه درتکرارها فقط یه قسمت اضافه میشه .
ممنون مدیر جون که واسه تاپیکها وقت میزارین سپاس کمه عزیزم فدات