سلام عزیزان
یه سوالی ب ذهنم خطور کرد و گیجم کرد اگر کسی میدونه لطفا راهنمایی کنه ممنون میشم
یه زبان ک تعداد a,b,c برابر باشد وn>1 مستقل از متن نیست یعنی با ماشین پشته ای استاندارد نمیشه حلش کرد ولی با ماشین دو پشته ای میشه طراحی کرد حالا این وسط این زبان مستقل از متن هست یا حساس ب متن؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ماشین دو پشته ای تواناییش در حد تورینگه چون فرض کن جفتشون روی نوار کار میکنن اونوقت فرق تورینگ و ماشین پشته ای اینه که تورینگ به همه جای نوار دسترسی داره ولی پشته فقط به سمت چپ ترین خونه غیر blank.
حالا اگه دوتا پشته باشه تمام کار های تورینگو میشه شبیه سازی کرد به این صورت که اگه ماشین تورینگ با خونه ی iام کار داشت تمام محتویات بالای خونه iام تو پشته اول انتقال داده میشه به پشته دوم و عملیات لازم روی اون خونه انجام میشه و دوباره محتویات به سر جاش برگردونده میشه.
حالا a^n b^n c^n مستقل از متن نبودنش رو به راحتی با لم پمپاژ یا لم اوگدن میشه نشون داد.
برای اثبات حساس به متن بودنش هم میشه یا گرامر طول افزایشی براش طراحی کرد یا ماشین lba.