تصمیم‌پذیری و مسائل تصمیم

کدام یک از مسائل زیر، در مورد یک اتوماتون پشته‌ای غیرقطعی (NPDA) دلخواه به‌نام M، تصمیم‌پذیر (decidable) است؟

کدام مورد، درست است؟

چه تعداد از گزاره‌های زیر درست است؟ هر زبان تشخیص‌ناپذیر تورینگ، تصمیم‌ناپذیر است. مجموعه همه زبان‌های نامنظم روی یک الفبا، یک مجموعه شمارای نامتناهی است. مجموعه همه ماشین‌های تورینگ روی یک الفبا، یک…

زبان پذیرفته شده توسط پذیرنده پشته‌ای PDA روبه‌رو، کدام گزینه است؟ ( N_a(w) تعداد حرف a در رشته w را مشخص می‌کند.)

کدام‌یک از گزاره‌های زیر درست است؟

کدام‌یک از مسائل زیر برای یک ماشین تورینگ دلخواه تصمیم‌پذیر (decidable) هستند؟