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

ماشین تورینگ $M$ با جدول انتقال زیر داده شده است (هر درایه (حالت بعدی، نماد نوشته‌شده، حرکت)؛ $ نشانگر ابتدای نوار و # نماد تهی است):

state \ symbol |    $          0          1          #
--------------+----------------------------------------------
  q0          | (qR,$,R)      —          —          —
  qR          |   —        (qR,0,R)   (qR,1,R)   (q1,#,L)
  q1          | (qf,1,L)   (qL,1,L)   (q1,0,L)     —
  qL          | (qf,$,R)   (qL,0,L)   (qL,1,L)     —
  qf          |   —          —          —          —

کدام‌یک از دو مورد زیر، درباره $M$ درست است؟

I. q0 $1001 $\vdash^{*}$ $ qf 1010

II. q0 $101010 $\vdash^{*}$ $ qf 101110