۰
subtitle
ارسال: #۱
  
wwمستقل از متن یا نه؟
سلام دوستان عزیزم
[tex]L=\left \{ ww | w\epsilon\left \{ a,b \right \}^{*} \right \}[/tex]
این زبان مستقل از متن نیست اثبات عدم مستقلال متنی این زبان با فرض
[tex]w=a^{m}b^{m}a^{m}b^{m}[/tex]
چه طوری میشه؟
تو لینز خلاصه گفته میشه لطف کنین توضیح بدین؟
[tex]L=\left \{ ww | w\epsilon\left \{ a,b \right \}^{*} \right \}[/tex]
این زبان مستقل از متن نیست اثبات عدم مستقلال متنی این زبان با فرض
[tex]w=a^{m}b^{m}a^{m}b^{m}[/tex]
چه طوری میشه؟
تو لینز خلاصه گفته میشه لطف کنین توضیح بدین؟
۰
ارسال: #۲
  
wwمستقل از متن یا نه؟
سلام. اگه درنظر بگیری 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) و یا حالتی مشابه حالت اولی برای حراقل یکی از حروف پیش میاد.
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) و یا حالتی مشابه حالت اولی برای حراقل یکی از حروف پیش میاد.
۰
ارسال: #۳
  
wwمستقل از متن یا نه؟
یکی از دوستان ج رو خصوصی دادن منتهی من پاسخ رو میزارم واسه همه
کافیه رشته رو طوری تجزیه کنیم که تزریق منجر به تولید رشته ای خارج زبان بشه
ماvxy را بطول کمتر از m از وسط رشته انتخاب میکنیم بعد vو y رو تزریق میکنیم که منجر میشه که رشته ای خارج زبان تولید بشه
مرسی از دوستانی که کمک میکنن خدا خیرشون بده
درسته؟
کافیه رشته رو طوری تجزیه کنیم که تزریق منجر به تولید رشته ای خارج زبان بشه
ماvxy را بطول کمتر از m از وسط رشته انتخاب میکنیم بعد vو y رو تزریق میکنیم که منجر میشه که رشته ای خارج زبان تولید بشه
مرسی از دوستانی که کمک میکنن خدا خیرشون بده
درسته؟
۰
ارسال: #۴
  
RE: wwمستقل از متن یا نه؟
سلام
همون uvxyzای که کتاب در نظر بگیرید حالا با تکرار v وy به تعداد i فقط یک سمت تعداد a و b ها اضافه میشه و در نتیجه رشته ی مورد نظر در زبان نیست این حالت یکی از بدترین حالتهایی هست که حریف میتونه انتخاب کنه حالت دیگه هم میتونه به صورت زیر باشه
اگه vxy شما یک نوع سمبل باشن(یعنی یا a باشن یا b) با توجه به محدودیت هایی نظیر(طول vxy کمتر از m)همیشه درتکرارها فقط یه قسمت اضافه میشه .
همون uvxyzای که کتاب در نظر بگیرید حالا با تکرار v وy به تعداد i فقط یک سمت تعداد a و b ها اضافه میشه و در نتیجه رشته ی مورد نظر در زبان نیست این حالت یکی از بدترین حالتهایی هست که حریف میتونه انتخاب کنه حالت دیگه هم میتونه به صورت زیر باشه
اگه vxy شما یک نوع سمبل باشن(یعنی یا a باشن یا b) با توجه به محدودیت هایی نظیر(طول vxy کمتر از m)همیشه درتکرارها فقط یه قسمت اضافه میشه .
۰
ارسال: #۵
  
wwمستقل از متن یا نه؟
ممنون مدیر جون که واسه تاپیکها وقت میزارین سپاس کمه عزیزم فدات
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close