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

ماشین تورینگ زیر براساس الفبای ورودی $\{a, b\}$ (با نماد تهی $\square$ و نماد نشانه‌گذاری $x$) به‌صورت زیر تعریف شده است (نمودار حالت‌ها):

• $q_0 \xrightarrow{a \to \square,\, R} q_1$
• $q_1 \xrightarrow{a \to a,\, R} q_1$، $\ q_1 \xrightarrow{x \to x,\, R} q_1$
• $q_1 \xrightarrow{b \to x,\, R} q_2$
• $q_2 \xrightarrow{\square \to \square,\, L} q_6$، $\ q_2 \xrightarrow{b \to b,\, L} q_3$
• $q_3 \xrightarrow{x \to x,\, L} q_3$، $\ q_3 \xrightarrow{a \to a,\, L} q_4$
• $q_4 \xrightarrow{a \to a,\, L} q_4$، $\ q_4 \xrightarrow{\square \to \square,\, R} q_5$، $\ q_4 \xrightarrow{x \to x,\, R} q_5$
• $q_5 \xrightarrow{a \to x,\, R} q_1$
• $q_6 \xrightarrow{x \to x,\, L} q_6$، $\ q_6 \xrightarrow{\square \to \square,\, R} q_{acc}$

کدام گزینه درخصوص این ماشین تورینگ درست است؟

(a) دنباله‌ای از محاسبات به‌صورت $q_0\, aa\, bb \vdash^* \square\, q_5\, axb \vdash \cdots$ وجود دارد.

(b) برای هر رشته ورودی هیچ دنباله‌ای نامتناهی از محاسبات وجود ندارد و در نتیجه محاسبات در جایی متوقف خواهدشد.