{a^{n}b^{m}c^{n} | n>=m>= 0}
[attachment=2718]
نمی دونم واقعا اما فکر می کنم میشه اول به ازای n ، n تا بزاری تو پشته، بعد به ازای هر b اون متغیری که گذاشتی تو پشته بخونی و باز همون رو پوش کنی. اگه تعداد b بیشتر بشه دیگه به جای میرسه که نمی تونه چیزی رو پاپ کنه پس ادامه کار قطع میشه. اگه هم کمتر از تعداد n باشه به سلامت میره رو c و به ازاری هر c یه متغیر پاپ میکنه و پشته هم در انتها خلی میشه.
اما میگن این مستقل از من نیست.
{a^{n}b^{m}c^{n} | m> =n>= 0}
[attachment=2719]
میشه یکی توضیح بده لطفا فرق این دوتا چیه و کدومش مستقل هست و کدومش نیست؟
با تشکر.
هیچکدوم مستقل از متن نیستن. جفتشو میشه با لم تزریق رد کرد. یا باید تعداد cها رو با aها برابر کنیم یا شرط تعداد b رو درنظر بگیریم.
توی استدلالتو گفتین "دوباره همون متغیر رو پوش کنیم" اگه اینکارو بکنیم که تعداد aهای توی پشته با خوندن b تغییر نمیکنه و نمیتونیم بین m و n مقایسه داشته باشیم.
رشته a^nb^nc^n رو درنظر بگیرید که توی هردو زبان پذیرفتست. با لم تزریق میشه ثابت کرد مستقل از متن نیست. اگه vy فقط جزء aها یا cها باشه که تعدادشون به ازای i=2 برابر نیست. اگه فقط جزء bها باشه که با قراردادن i=0,2 مثال نقض داریم. واگه بینشون باشه یکی از دوحالت قبل پیش میاد.
two terms are not a context free language