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

الف) یک Mid PDA یک PDA توسعه‌یافته است که می‌تواند وسط پشته را بخواند. در واقع تابع انتقال در Mid PDA تابع چهار چیز است: نماد ورودی، نماد بالایی پشته، حالت فعلی ماشین و نماد وسط پشته. ( اگر پشته k نماد داشته باشد، ⌈k/2⌉اُمین نماد از بالا، نماد وسط پشته خواهد بود و اگر پشته تهی باشد λ نماد وسط پشته درنظر گرفته می‌شود.) وقتی Mid PDA حرکت می‌کند، حالت خود را تغییر می‌دهد، نمادی در پشته درج می‌شود و حداکثر یک نماد از ورودی خوانده می‌شود. ( همان‌طور که گفته شد نماد وسط پشته در حرکت این ماشین مؤثر است.)

ب) یک 2PDA یک PDA با دو پشته متمایز است. حرکت در 2PDA براساس حالت فعلی ماشین، نمادهای بالایی پشته‌ها و نماد ورودی است. وقتی حرکتی انجام می‌شود، ماشین حالت خود را تغییر می‌دهد، چیزی در پشته اول درج می‌شود، چیزی در پشته دوم درج می‌شود ( مستقل از پشته اول) و حداکثر یک نماد از ورودی می‌خواند.

کدام‌یک از این دو ماشین Mid PDA و 2PDA از PDA معمولی قوی‌تر است؟