تالار گفتمان مانشت

آیا این زبان مستقل از متن قطعی هستش؟اصن مستقل از متن هست؟

[tex]L=\{a^mb^mc^n:0≤m≤n≤2m\}[/tex]

با سلام دخیر دوست عزیز اصلا مستقل از متن نیست که بخواهد قطعی باشه
شما وقتی a ها را بریزی داخل پشته بعدش که b ببینی به ازای هر a یک b پاپ می کنی دیگه اون موقع m نداری که بخوای با n قیاس کنی که ازش کمتر باشه با یک پشته نمی تونی پیاده اش کنی پس مستقل از متن نیست موفق باشید.

(07 بهمن 1393 01:59 ب.ظ)Hamid_0311 نوشته شده توسط: [ -> ]با سلام دخیر دوست عزیز اصلا مستقل از متن نیست که بخواهد قطعی باشه
شما وقتی a ها را بریزی داخل پشته بعدش که b ببینی به ازای هر a یک b پاپ می کنی دیگه اون موقع m نداری که بخوای با n قیاس کنی که ازش کمتر باشه با یک پشته نمی تونی پیاده اش کنی پس مستقل از متن نیست موفق باشید.

حالا اگه زبان به صورت [tex]L=\{a^mb^mc^n\: :\: \: 0\le m\le n\}[/tex] بود مستقل از متن میشد؟!

با سلام نخیر دوست عزیز بازم نمیشد
ماشین زبان های مستقل از متن چیه؟ یک PDA
ماشینی که حافظه اش یک پشته است حافظه ی دیگه ای نداره (البته به غیر بافری که رشته ی ورودی روش هست منظورمه)
خوب شما وقتی بیای رشته را پیمایش کنی و a ها را بریزی داخل پشته بعد از اینکه به b رسیدی میگی به ازای هر یک b یه دونه a از پشته پاپ کن خوب وقتی مساوی باشن پشته خالیه و رسیدیم به c از کجا بدونیم اون مقدار m چندتا بود که بخوایم بگیم از مقدار n کمتر باشه؟؟ پس برای نگهداری مقدار m یک حافظه ی دیگه ای لازم داریم پس نمیتونیم با ماشین پشته ای حلش کنیم پس مستقل از متن نیست
موفق باشید