سوال ۸۹ کنکور ارشد علوم کامپیوتر ۱۴۰۴ — فرض کنید M یک ماشین تورینگ معمولی است با این تفاوت که امکان حرکت به…

Question

فرض کنید M یک ماشین تورینگ معمولی است با این تفاوت که امکان حرکت به چپ را ندارد اما می‌تواند در همان خانه بماند. کدام مورد درخصوص M درست است؟

Accepted Answer

M قدرت تشخیص زبان‌های منظم را دارد ولی قدرت تشخیص زبان‌های مستقل از متن را ندارد.

Answer

M معادل ماشین تورینگ معمولی است.

Answer

M قدرت تشخیص زبان‌های منظم را ندارد.

Answer

M قدرت تشخیص زبان‌های مستقل از متن را دارد ولی قدرت آن از ماشین‌های تورینگ معمولی کمتر است.

The restriction makes the head one-way