سلام
در لم تزریق برای زبان های مستقل از متن فرض کنید چهار حالت به وجود اومده ، برای اینکه بگیم مستقل از متن نیست اگر یکی از این حالت ها رد بشه کافیه یا اینکه حتما باید تمام حالت ها رو بررسی کنیم و ثابت کنیم برای همه حالت ها عضو زبان نیست .
مثلا برای اثبات اینکه a^nb^nc^n یک زبان مثلا a^mb^mc^m رو در نظر میگیریم که خودش چند حالت داره :
حالت اول : u,v,x,y رو از a در نظر میگیریم و بقیه رو z
حالت دوم : uvx رو از a و y رو از b و z رو از b و c
حالت سوم : و الی آخر
یکی از حالت ها جواب نده کافیه؟ یا باید تمام حالت ها رو بررسی کنیم؟
باید تمام حالت ها بررسی بشند.
این به خاطر اینه که نحوه ی انتخاب قسمت های uvxyz دست حریف شماست ( همون بازی داخل کتاب لینز).
پس شما باید تمام حالت هایی که حریف می تونه انتخاب کنه رو بررسی کنید.
(۱۰ خرداد ۱۳۹۳ ۰۵:۵۷ ب.ظ)alirezad نوشته شده توسط: باید تمام حالت ها بررسی بشند.
این به خاطر اینه که نحوه ی انتخاب قسمت های uvxyz دست حریف شماست ( همون بازی داخل کتاب لینز).
پس شما باید تمام حالت هایی که حریف می تونه انتخاب کنه رو بررسی کنید.
خب اگه یکی از حالت ها هم جواب نده ، نمیشه چیزی در موردش گفت ، یعنی باید تمام حالت ها رد بشن تا بتونیم بگیم مستقل از متن نیست؟
(۱۰ خرداد ۱۳۹۳ ۰۷:۱۸ ب.ظ)gmh1993 نوشته شده توسط:(10 خرداد ۱۳۹۳ ۰۵:۵۷ ب.ظ)alirezad نوشته شده توسط: باید تمام حالت ها بررسی بشند.
این به خاطر اینه که نحوه ی انتخاب قسمت های uvxyz دست حریف شماست ( همون بازی داخل کتاب لینز).
پس شما باید تمام حالت هایی که حریف می تونه انتخاب کنه رو بررسی کنید.
خب اگه یکی از حالت ها هم جواب نده ، نمیشه چیزی در موردش گفت ، یعنی باید تمام حالت ها رد بشن تا بتونیم بگیم مستقل از متن نیست؟
دقیقا
(۱۰ خرداد ۱۳۹۳ ۰۷:۳۷ ب.ظ)alirezad نوشته شده توسط: دقیقا
ممنونم