کدام گزینه صحیح است؟
۱) اگر P یک ماشین PDA باشد، ممکن است کلمه ورودی w موجود باشد به طوری که کلیه مسیر‌های محاسبه ماشین P با ورودی w به صورت loop نامتناهی باشند.
۲) برای هر زبان مستقل از متن، یک ماشین PDA وجود دارد به طوری که برای هر کلمه ورودی w ماشین فقط دارای یک مسیر محاسبه یکتا است.
۳) برای هر ماشین PDA، و هر ورودی داده شده‌ی w، تعداد پیکربندهای ماشین با ورودی w حتما متناهی است.
۴) برای هر گرامل مستقل از متن فقط دقیقا یک ماشین PDA معادل وجود دارد.
من فکر می‌کردم گزینه‌ی ۳ درست باشه ولی کتاب زده گزینه‌ی ۱. مگر PDA هم می‌تونه همه‌ی مسیرهاش توی inifine loop بیافته و halt نشه؟
همان گزینه‌ی ۱ درست هست. اگر λ-transition نداشته باشیم آنگاه اتوماتا‌ی پشته‌ای به هیچ وجه وارد حلقه نامتناهی نمی‌شود. اما در غیر این صورت این امکان هست که رشته‌ای PDA را به infinite loop ببرد. حتی می‌توان PDAای طراحی کرد که به ازای هر ورودی وارد infinite loop بشود این در حالی است که PDA ما حالت final نداشته باشد یا حالت final آن reachable نباشد.