(۰۸ اسفند ۱۳۸۹ ۱۰:۳۶ ق.ظ)mehrline نوشته شده توسط: اگه به سراغ کتاب لینز برین، در فصل ۴، توی یکی از تمرین‌ها، یه چیزی تو مایه های این رو داده. خوده لینز هم که من کتاب زبان اصلیشو خوندم، اینو حل کرده و ابتدای پاسخش میگه که " شاید تعجب کنید . ولی این CF هست". راه حلیم واسش داده. این یه استثنا بود که باید حفظش می کردی!!!
دومی وقتی منظمه، یعنی مستقل از متن هم هست
اگه دقت کرده باشی در کتاب لینز گفته که طول دو رشته برابر نباشه و درسته اون موقعه مستقل از متن است ولی من یادمه دکتر کارگهی همین سوالی که در کنکور آمده را حل کرده و گفت اگر طول دو رشته مساوی باشند اونموقعه مستقل ازمتن نیست
دلیلش هم این است که شما رشته اول را داخل پشته میریزید و زمانی که طول دو رشته برابر نباشه به راحتی با هر حرفی که از ورودی میخوانی یکی هم از پشته pop میکنی و مهم نیست که چی داری pop میکنی و زمانی که ورودی تمام شد نباید پشته خالی شده باشد آن وقت رشته پذیرفته میشه پس مستقل از متن است یا پشته خالی شده ولی رشته تمام نشده اون موقعه به یک حالتی میری که فقط رشته ورودی را مصرف کند و در آخر پذیرفته میشود
ولی زمانی که طول دو رشته برابر است شما رشته اول را در پشته قرار میدهید و ابتدای رشته به ته پشته میرود حالا شما باید چک بکنی که ابتدای رشته دوم آیا با ابتدای رشته اول یکسان است ؟ ولی این کار رانمیتونی بکنی چون که ابتدای رشته اول ته پشته میباشد پس نمیتونه مستقل ازمتن باشه
پس زبانش چی میشه ؟ من میگم حساس به متنه و راه حلم هم اینه
این زبان رشته های به طول زوج داره پس با کمک قواعد زبان های حساس به متن میانه رشته‌ها را بدست می آوریم سپس یک علامت میگذاریم مثلاً @ . حالا به ابتدای رشته میرویم و هر چی در ابتدا بود مثلاً a را تبدیل به x میکنیم و حرکت میکنیم تا به میانه برسیم سپس چک میکنیم ببینیم آیا در ابتدای میانه هم a داریم دوباره به ابتدای رشته میریم و حرف دوم را بررسی میکنیم مثلاً b است با y جایگزین میکنیم و بعد به میانه رشته میرویم و عناصری را که تا کنون چک کرده ایم پشت سر میگذاریم وسپس میبینیم آیا حرف بعدی در میانه b هست یا نه و این کار را تا آخر ادامه میدهیم تا نیمه اول به میانه برسد و در آخر این رشته را اگر در شرایط زبان صدق میکرد میپذیریم
