l مجموعه همه گرامرهای مستقل از متن است که زبانی نامتناهی را تولید میکند ایا l تصمیم پذیر است؟
- اتوماتون یک ماشین pda فاقد انتقال بلادرنگ است انگاه لزوما
برای هر ورودی ماشین دقیقا یک مسیر محاسبه یکتا دارد
برای هر ورودی ماشین حداکثر یک مسیر محاسبه یکتا دارد
زمان محاسبه هر ورودی متناهی است
زبان ماشین شامل کلمه پوچ است
(به نظر من هیچکدام صحیح نیست.نظرتون چیه؟)
۲/به نظر من زمان محاسبه هر ورودی متناهی است.
که البته ربطی به بودن یا نبودن حرکت لاندا نداره و در هرصورت توی این ماشین زمان محاسبه ورودی متناهی هست.
۱/یعنی اینکه تشخیص بدیم یک گرامر مستقل از متن زبان چه زبانی رو تولید میکنه و آیا این زبان برابر زبان مورد سوال هست یا نه.
که میشه این سوال که آیا دو تا زبان مستقل از متن برابرند یا نه که فک کنم تصمیم ناپذیره.
جواباش رو دارین؟
اگر دارین بزارین لطفا.