سوال ۹۲ کنکور ارشد علوم کامپیوتر ۱۴۰۰

فرض کنیم Q یک اتوماتای شبیه به PDA باشد با این تفاوت که به جای پشته مجهز به یک نوار باشد. به عبارت دیگر، Q ماشینی متناهی‌الحالت است که با توجه به نماد ورودی فعلی، حالت فعلی و نماد جلویی نوار حرکت می‌کند. تابع انتقال این ماشین اجازه می‌دهد که حالت خود را تغییر دهد، نماد جلویی را از نوار حذف کند و نمادی به آخر نوار اضافه کند. قدرت ماشین Q در تشخیص زبان‌ها:

۱) کمتر از PDA ها است. ۲) به اندازه‌ی PDA ها است. ۳) به اندازه‌ی ماشین‌های تورینگ است. ۴) کمتر از ماشین‌های تورینگ و بیشتر از PDA ها است.